Question about about halting problem and this particular function

  • I
  • Thread starter olgerm
  • Start date
  • Tags
    Set theory
In summary, the conversation discusses the most well-known proof of the undecidability of the halting problem, which involves a hypothetical function H1 that can determine whether a program halts on a given input. It is shown that such a function cannot exist, as it leads to a contradiction in both cases when applied to a function D that is defined based on its input. The conversation also considers the existence of a modified function F3, but it is proven that this function is also non-computable. This further reinforces the understanding that there is a widespread misunderstanding about the halting problem.
  • #1
olgerm
Gold Member
531
34
The most known proof of undecidability of the halting problem is about like that:

Code: 
#assume we have an hypothetical function that can determine whether any program P would halt on input i.
def H1(P, i):
    """
    H1 is a hypothetical function that determines whether program P halts on input i.
    Returns True if P halts on i, and False if P runs forever on i.
    """
    raise NotImplementedError#We also have such function:
def D(P):
    if H1(P, P):
        while True:
            pass  # Loop indefinitely.
    else:
        return  # Halt.
Now consider D(D). There are two cases:case1:
If H1(D, D)==False then, by definition of D, D(D) must halt.
But if H1(D, D)==False then, by definition of H1, D(D) must never halt.

case2:
H1(D,D)==True , then by the definition of D, D(D) must never halt.
But if H1(D, D)==True, then, by definition of H1, D(D) must halt.

In either case, we have a contradiction.
Therefore function that determines whether any program P halts on any input i does not exist.It proves that function (lets call this function H1) with following properties cannot exist:
  • it takes 2 arguments (lets call these x1 and x2)
  • returns False if call x1(x2) stays in infinit loop.
  • returns True if call x1(x2) ever returns.
I noticed that this proof would not prove that function (lets call this function F3) with following properties would not exist:
  • accepts 2 arguments(lets call these x1 and x2).
  • returns false if x1==x2.
  • returns False if x1!=x2 and call x1(x2) stays in infinit loop.
  • returns True if x1!=x2 and call x1(x2) ever returns.
If function F3 indeed exists it would show halting problem quite differently than how many people think of it.With very similar proof to most known proof of halting problem we could also prove that function (lets call this function G) with following properties would not exist:
  • accepts 1 argument(lets call it x).
  • returns NOT x(x) .
It could not exist because from it's definition we can conclude that G(G)==not G(G) . This is a true statement, that such function does not exist.
Does function F3 exist or function with such properties can not exist?
Does this make you think that there is a wide spread missunderstanding about halting problem?
 
Last edited:
Physics news on Phys.org
  • #2
You can make trivial modifications to D to prove F3 does not exist. E.g. D stays as you wrote, and we define D2 to be the same as D, except if P is the function that immediately returns true on any input, we loop. Indefinitely. D(D2) has all the same problems as D(D).
 
  • #3
Office_Shredder said:
You can make trivial modifications to D to prove F3 does not exist. E.g. D stays as you wrote, and we define D2 to be the same as D, except if P is the function that immediately returns true on any input, we loop. Indefinitely. D(D2) has all the same problems as D(D).
I do not see how D2 would prove, that F3 does not exist. In call D2(D2) first argument of D2 is not a function, that returns True on every input.
 
  • #4
olgerm said:
I do not see how D2 would prove, that F3 does not exist. In call D2(D2) first argument of D2 is not a function, that returns True on every input.

The point is ##F_3(D,D_2)## has issues (note only one of these is ##D_2##!).
 
  • #5
I agree with @Office_Shredder that such a function F3 isn't a computable function. Let me write the definition of this function ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## in my own wording. Given any inputs ##x_1,x_2 \in \mathbb{N}##, we evaluate the ##F_3(x_1,x_2)## as follows:
(1) If ##x_1=x_2## then we have ##F_3(x_1,x_2)=0##
(2) If ##x_1\neq x_2## and the program with index ##x_1## loops forever on input ##x_2## then return ##F_3(x_1,x_2)=0##
(3) If ##x_1\neq x_2## and the program with index ##x_1## halts on input ##x_2## then return ##F_3(x_1,x_2)=1##

This function ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## is known to be non-computable. For this consider a function ##G:\mathbb{N} \rightarrow \{0,1\}## defined as follows for any input ##x \in \mathbb{N}##:
(1) If the program with index ##x## loops forever when given the input ##0## then ##G(x)=0##.
(2) If the program with index ##x## halts when given the input ##0## then ##G(x)=1##.Now with a bit of work, one can show that the function ##G:\mathbb{N} \rightarrow \{0,1\}## is not a computable function. I think one would tend to find this result in a number of introductory texts (but I don't know a reference off-hand) either in the main text or as an exercise. This problem of ##G## being a computable function or not is sometimes called "halting problem on zero or empty input".Now let's suppose that ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## was a computable function. Then, almost immediately, this implies that ##G:\mathbb{N} \rightarrow \{0,1\}## must be a computable function too. Since that is not true we infer that our assumption of ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## being a computable function was wrong.
 
Last edited:
  • #6
Office_Shredder said:
The point is ##F_3(D,D_2)## has issues (note only one of these is ##D_2##!).
What is the issue? I do not see how this proves that F3 can not exist.
*F3(D,D2)==True
*form definition of F3 we know that if F3(D,D2)==True then D(D2) returns (in other words halts)
*from definition of D we know that if D(D2) to ever returns then F3(D2,D2)==False
*from definition of f3 we know that if F3(D2,D2)==False then D2(D2) must stay in infinit loop
this does not lead to contradiction.
 
  • #7
olgerm said:
this does not lead to contradiction.
It is clear that it does.

Let ## A = \left ( F_3(D, D_2) \text{ is true} \right ), B = \left ( D(D_2) \text{ returns} \right ) ##. Your statements then become:

olgerm said:
form from the definition of F3 we know that if F3(D,D2)==True then D(D2) returns (in other words halts)
## A \implies B ##

olgerm said:
form from the definition of D we know that if D(D2) to ever returns then F3(D2,D2)==False
## B \implies \neg A ##

Is the contradiction clear now?
 
  • #8
I described one way of showing ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## as non-computable in post#5. But that was very indirect. However, I think the most direct way to show that ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## is not a total computable function is as follows.

Suppose ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## was computable. Then the usual two-argument halt function ##Halt:\mathbb{N}^2 \rightarrow \{0,1\}## must be computable. Since that isn't true, our assumption of ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## being computable must be wrong.

So, let's see why ##Halt:\mathbb{N}^2 \rightarrow \{0,1\}## must be computable if ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## was computable. Let's suppose we have to determine ##Halt(a,b)## for some arbitrary ##a,b \in \mathbb{N}##. That is we have to determine whether the program with index ##a## halts when given the input ##b##. Let's call the program with index ##a## as P1. If ##a \neq b## then we just call ##F_3(a,b)## to determine ##Halt(a,b)##.Now let's suppose we had ##a=b## and we have to determine ##Halt(a,a)##. We modify this program P1 to make a program with index ##c## (which we call P2). Here is a sketch of P2 (here ##t## is any variable):
t:=t+1
t:=t-1
body of P1

In other words, we make an inconsequential change to program P1 to get P2. Most importantly, both programs P1 and P2 halt and loop on exactly the same inputs. So to determine ##Halt(a,a)## we just make a call to the function ##F_3(c,a)##. Since ##c \neq a## , we note that both ##Halt(a,a)## and ##F_3(c,a)## will return exactly the same value.
 
Last edited:
  • #9
pbuk said:
## A \implies B ##
## B \implies \neg A ##

Is the contradiction clear now?
## (A \implies B) \land (B \implies \neg A) ## is itself is not contradictory. it is same as just ##\neg A## . Possible values for A and B for this case:
  • A=False and B=False
  • A =False and B =True

and
pbuk said:
## B \implies \neg A ##
it is untrue because ##B = \left ( D(D2) \text{ returns} \right ) ##
not that ##B = \left ( D2(D2) \text{ returns} \right ) ##
 
  • #10
olgerm said:
## (A \implies B) \land (B \implies \neg A) ## is itself is not contradictory. it is same as just ##\neg A## . Possible values for A and B for this case:
Yes, it is just the same as ## \neg A ##. But we don't have ## \neg A ## do we, because sometimes ## F_3(D, D_2) \text{ is true} ##?

olgerm said:
##B = \left ( D(D2) \text{ returns} \right ) ## not that ##B = \left ( D2(D2) \text{ returns} \right ) ##
I assumed this was a typo, why are you comparing statements that are talking about completely different things?

This is madness, let's start again.

olgerm said:
I noticed that this proof would not prove that function (lets call this function F3) with following properties would not exist:
  • accepts 2 arguments(lets call these x1 and x2).
  • returns false if x1==x2.
Even if you could write such a function it would sometimes give the wrong answer:
Python: 
def alwaysHalts(x1):
  return x1

print(F3(alwaysHalts, alwaysHalts)) # False

olgerm said:
If function F3 indeed exists it would show halting problem quite differently than how many people think of it.
Yes, so the fact that a working F3 would overturn the work of Alonzo Church, Alan Turing and the whole of the rest of computation theory should alert you to the likelihood of its existence.

olgerm said:
With very similar proof to most known proof of halting problem we could also prove that function (lets call this function G) with following properties would not exist:
  • accepts 1 argument(lets call it x).
  • returns NOT x(x) .
No, that function does exist, however it does not terminate given itself as an input. You don't need any complicated proof for that, and you don't even need the negation, you can immediately see that it creates an infinite loop:
Python: 
def sometimesHalts(x):
  return x(x)

print(sometimesHalts(sometimesHalts)) # Infinite recursion.
print(sometimesHalts(x: type(x))
 
Last edited:
  • #11
pbuk said:
No, that function does exist, however it does not terminate given itself as an input.
it does not exist. If you think it does exist try to answer following questions:
  • What you think G(G) should return?
  • Is that what you think G(G) should return in accordance with definition of G?
A diffenernt funciont (lets call it G2) that that has following properties:
  • accepts 1 argument(lets call it x).
  • returns x(x).
does exist. from info that we have about G2 we do not know if G2(G2)==True or G2(G2)==False
pbuk said:
Yes, so the fact that a working F3 would overturn the work of Alonzo Church, Alan Turing and the whole of the rest of computation theory should alert you to the likelihood of its existence.
pbuk said:
I assumed this was a typo, why are you comparing statements that are talking about completely different things?
I do not understand what are you trying to say by these.
pbuk said:
Even if you could write such a function it would sometimes give the wrong answer:
I do not understand what you mean. In what sense would this be wrong? what is "wrong answer"? By definition it does have to return False if its 2 arguments are equal. even if call arg1(arg2) ever returns.
 
Last edited:
  • #12
olgerm said:
it does not exist
Yes it does (this is a pointless argument).

olgerm said:
it does not exist
I showed you how to write it in #10; for the avoidance of doubt
pseudocode: 
def G(x):
  return not x(x)

olgerm said:
  • What you think G(G) should return?
  • Is that what you think G(G) should return in accordance with definition of G?
In accordance with the definition of G, G(G) does not return anything, it enters an infinite loop. In the terminology of computation theory we say it does not halt.

olgerm said:
A diffenernt funciont (lets call it G2) that that has following properties:
Please stop making up more and more functions, this is off-topic and it is your own topic!

olgerm said:
I do not understand what you mean. In what sense would this be wrong? what is "wrong answer"?
It would be wrong because F3 is supposed to be a halting decider (otherwise it has no relevance to anything in this thread), and False is the wrong answer for my function alwaysHalts.
 
  • #13
pbuk said:
It would be wrong because F3 is supposed to be a halting decider (otherwise it has no relevance to anything in this thread), and False is the wrong answer for my function alwaysHalts.
I do not think that this particular comment is accurate. The thing is that the function ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## is supposed to be different from the function ##Halt:\mathbb{N}^2 \rightarrow \{0,1\}##. In other words, they are not supposed to agree on all inputs. That follows because of the definition of ##F_3##.

However, the question was whether the function ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## is a (total) computable function or not. The answer is no. I gave one answer in post#5. The other answer is post#8 is simpler though. The point is that if ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## really was a total computable function then ##Halt:\mathbb{N}^2 \rightarrow \{0,1\}## would be a total computable function too. Since the latter isn't a total computable function, we can conclude that ##F_3:\mathbb{N}^2 \rightarrow \{0,1\}## isn't a total computable function either.

As a side note, also it is sometimes common as a short-hand to sometimes write "total computable function" as "computable function".

olgerm said:
Does function F3 exist or function with such properties can not exist?
Since there has been some confusion in this thread I feel it is also worth clearing this point. Strictly speaking the answer to your question is "yes". Of course the function F3 exists. In fact, it is a "partial computable function". Even the two argument halt function ##Halt## is a partial computable function.

However, it is clear given the context of question that what you are asking is whether F3 is a "total computable function" or not? The answer to this is no. Same goes for the the ##Halt## function.
 
Last edited:
  • Like
Likes olgerm
  • #14
olgerm said:
this proof would not prove that function (lets call this function F3) with following properties would not exist
Yes, it does, because your function F3 is logically equivalent to this:

Code: 
def F3(x1, x2):
    if x1 == x2:
        return False
    else:
        return H1(x1, x2)

Since we have already proven that H1 does not exist, F3 cannot exist either.
 
  • #15
So back on topic, from your first post:
olgerm said:
I noticed that this proof would not prove that function (lets call this function F3) with following properties would not exist:
  • accepts 2 arguments(lets call these x1 and x2).
  • returns false if x1==x2.
  • returns False if x1!=x2 and call x1(x2) stays in infinit loop.
  • returns True if x1!=x2 and call x1(x2) ever returns.

This is not correct: the "standard" proof to the "standard" halting problem also proves that your function F3 cannot exist. Consider the following function:

pseudocode: 
def A(x):
  if F3(A, x):
    while True:
      pass
  return x

If F3(A, 1) returns True then it has determined that A(1) halts, however if F3(A, 1) is True then A(1) enters an infinite loop, a contradiction.

On the other hand if F3(A, 1) returns False then it has determined that A(1) does not halt, however if F3(A, 1) is False then A(1) halts returning 1, a contradiction.
 
  • Like
Likes SSequence
  • #16
PeterDonis said:
Yes, it does, because your function F3 is logically equivalent to this:

Code: 
def F3(x1, x2):
    if x1 == x2:
        return False
    else:
        return H1(x1, x2)

Since we have already proven that H1 does not exist, F3 cannot exist either.

Strictly speaking this argument is not accurate. The thing is that if a function is using ##Halt## function in its definition, it does not necessarily imply that the given function is not a total computable function. Consider the example of following definition of function ##f:\mathbb{N}^2 \rightarrow \mathbb{N}##:
##f(x,y)=x+y+Halt(x,y)## if ##Halt(x,y)## is false
##f(x,y)=x+y+Halt(x,y)-1## if ##Halt(x,y)## is true
This function just gives ##f(x,y)=x+y## even though it uses ##Halt## function in its definition.
The situation here is similar to how if we allow ordinary programs to make call to "Halt" oracle then some oracle-programs will indeed produce (total) functions that are "non-computable". However, some oracle-programs will also produce (total) functions that are "computable functions".
 
  • #17
SSequence said:
This function just gives ##f(x,y)=x+y## even though it uses ##Halt## function in its definition.
Only because Halt can be logically eliminated from the definition. That is not the case for the definition of F3 that I gave.

To put this another way: if you actually tried to implement your function ##f## as you define it, it would not work, because Halt does not exist. You would have to reimplement the function as the logically equivalent version that does not use Halt at all, in order to actually run it. But in the case of F3, there is no way to reimplement it to a logically equivalent version that does not call Halt at all.
 
  • Like
Likes pbuk
  • #18
Yes, indeed informally you are right about redundancy. Also, you are right about F3 being non-implementable on computer.

Though note here that the OP's function can be stated as equivalent to an oracle-program [that is a program equipped with an extra function to determine truth value of ##Halt:\mathbb{N}^2 \rightarrow \{0,1\} ##]. Note that we are just talking about a mathematical definition of a function here. The question of whether ##Halt## is computable or not doesn't effect whether the given function is mathematically well-defined or not. The function by OP is well-defined.Side Note:
Somewhat separate from this, in general it is not clear to me whether we can easily tell whether a given use of ##Halt## is redundant (in an oracle-program that is). Consider it this way. Suppose we have a program of 1000 lines with ##Halt## command placed on some specific subset of those lines. However, if I am not mistaken, this problem of determining whether certain lines will be visited by a program or not is also known to be not decidable. So, in an informal sense, if I am not mistaken then determining whether the call to ##Halt## function will ever even occur once in the first place in an "oracle-program" can be made equal to arbitrarily difficult number-theoretic problems. In summary, it seems to me that determining whether a given use is redundant or not can get quite non-trivial.
 
  • #19
SSequence said:
an oracle-program
This puts us into a different mathematical domain, which probably should go in a separate thread, so this thread can stay focused on the standard halting problem.
 
  • Like
Likes pbuk
  • #20
SSequence said:
The function by OP is well-defined.
Only if you assume that the Halt function exists. Which it doesn't within the mathematical domain of the standard halting problem. As I noted in post #19, considering "oracle" programs puts us into a different mathematical domain which is off topic for this thread.
 
  • Like
Likes pbuk
  • #21
SSequence said:
this problem of determining whether certain lines will be visited by a program or not is also not decidable
In the general case, I believe this is correct. However, the specific program you gave in post #16 is not an example of this; it is logically possible to show that all of the calls to Halt can be logically eliminated, which makes the question of which of them in the original version would be visited moot.
 
  • Like
Likes olgerm and pbuk
  • #22
You are right that in the specific example I gave in post#16 there is always going to be a call to ##Halt## if we write the definition in terms of oracle-program.

==================

Anyway, I will try to give one more example to try to illustrate what I am saying. Let ##Halt:\mathbb{N}^2 \rightarrow \{ 0, 1\}## be the usual two input halt function. We have ##Halt(x,y)=1## iff the program with index ##x## halts on input ##y## (and if it loops forever we get ##Halt(x,y)=0##).

Consider a function ##f_a: \mathbb{N} \rightarrow \mathbb{N}## for some specific natural number ##a##. We define ##f_a(x)## as follows for any arbitrary ##x \in \mathbb{N}##:
##f_a(x)=Halt(a,x)##
Given some specific ##a## the problem of determining whether the function ##f_a: \mathbb{N} \rightarrow \mathbb{N}## is a total computable function or not can be anything from extremely easy to extremely difficult [there will be some values of ##a## for which ##f_a## will be a computable function and others for which it will be non-computable].

What I am trying to say is that if a given definition uses the halt function, then it does not (by itself) render a function immediately non-computable. However, indeed it is true that the usage of halt function in a definition must make us quite wary that the definition can lead to a non-computable function.Note:
In the above, ##\mathbb{N}## can also be replaced with some suitable decidable subset of ##\Sigma^*##. Here ##\Sigma## is some finite set of alphabet and ##\Sigma^*## is the set of all finite strings using that alphabet.
 
Last edited:
  • #23
pbuk said:
pseudocode: 
def A(x):
  if F3(A, x):
    while True:
      pass
  return x

If F3(A, 1) returns True then it has determined that A(1) halts, however if F3(A, 1) is True then A(1) enters an infinite loop, a contradiction.

On the other hand if F3(A, 1) returns False then it has determined that A(1) does not halt, however if F3(A, 1) is False then A(1) halts returning 1, a contradiction.
This idea also seems accurate to me. Interesting use of a recursive call there.

It seems to me that the only thing we might have to be careful about is the possibility of the value of input variable x being equal to the index of the program/function ##A## [to avoid F3 vacuously returning ##0##]. But that could avoided easily.

Also, to be fair to OP, the function at the beginning of first post doesn't make any recursive calls. So, I think there is a non-trivial difference between these two ideas (even if the underlying concept is similar).Edit: Also, it doesn't seem to me that you need to return any specific number for your routine/function ##A##. So instead of:
return x
you could just write:
return //any number here
and the argument would still be right.
 
Last edited:
  • #24
SSequence said:
What I am trying to say is that if a given definition uses the halt function, then it does not (by itself) render a function immediately non-computable.
Yes, it does, unless the call to Halt cannot be eliminated by logical operations.

Your definition of ##f_a (x)## is not a definition of a single function. It is a family of definitions, one for each ##a##, and each such function does not call the general Halt function itself, it calls a function ##H_a (x)##, where ##H_a## is different for each ##a##. It is true that for some values of ##a##, ##H_a## will be computable, because calling ##H_a## is not the same as calling the general Halt function. (Or, to put it another way, the generic Halt function cannot exist by the proof already given; but it is still possible that for some values of ##a##, ##H_a## can exist.) The fact that some ##H_a## are computable is irrelevant to the fact that functions which call the generic Halt function are not computable unless the call to Halt can be eliminated by logical operations.
 
  • #25
pbuk said:
In accordance with the definition of G, G(G) does not return anything, it enters an infinite loop. In the terminology of computation theory we say it does not halt.
function is something that maps any arguemnt to some value. not returning anything is not an option. as i said in my first post in this thread: We call G aa function that ccepts 1 argument and returns negation of what call of its argument with itself as its argument would return. aka ##G(x)=\neg x(x)##

an algoritm can stay in infinit loop if call with some arguments, but all functions must return something on any argument
pbuk said:
It would be wrong because F3 is supposed to be a halting decider (otherwise it has no relevance to anything in this thread), and False is the wrong answer for my function alwaysHalts.
F3 is not same as the Halting function H1. If both arguments of F3 are equal then F3 returns False. Otherwise F3 returns same as Halting-function would return if callen with same arguments. read definition of F3 from the 1. post in this thread.
 
  • #26
olgerm said:
function is something that maps any arguemnt to some value. not returning anything is not an option.
Please explain then what you understand by "not halting" in this context?
 
  • #27
olgerm said:
F3 is not same as the Halting function H1.
This is obvious, however it suffers from the same problem as the function H1.
 
  • #28
PeterDonis said:
Yes, it does, because your function F3 is logically equivalent to this:

Code: 
def F3(x1, x2):
    if x1 == x2:
        return False
    else:
        return H1(x1, x2)

Since we have already proven that H1 does not exist, F3 cannot exist either.
F3 is indeed equalent to the code you posted. the sourcecode to define F3 using H1 is correct. You could implement F3 this way using H1.

Maybe it is my problem, but I do not see how does not prove that if H1 does not exist then F3 also does not exist. could you explain it going even to details, that seem too obvious to you to explain?

Pay attention to that: in call of F3 H1 is never called so that both arguments of H1 are equal. Maybe H1 CAN be simplified out of this implementation. I know my post may seem stupid, but be sure to check if you do not mistake here with something very basic.
 
Last edited:
  • #29
olgerm said:
Maybe it is my problem, but I do not see how does not prove that if H1 does not exist then F3 also does not exist. could you explain it going even to details, that seem too obvious to you to explain?
You are asking why it is not possible to use things that don't exist? It is difficult to take this seriously.
 
  • #30
pbuk said:
Please explain then what you understand by "not halting" in this context?
By not halting i mean that an algorithm would stay in an infinit loop. if an algoritm is implemented as a computerprogram and exectuted then the execution-process would never end itself. If a non-halting algrothm is implemented as python-subprogram(these are also called functions sometimes, but are not really mathematical functions), then the subprogram would never reach retrurn-statement.A program or an algorithm may stay in infitie cycle and never return(halt),

but

no function can stay in an infinit loop. There is no such function that does not return anything if called with some argument.Words "function" and "algorithm" have different meaning. For (at least some) functions it is possible to make algorithm that with same arguement returns same thing. But for algorithms, that never halt if called with some argument it is not possible to make a function that with same arguement returns same thing.
 
Last edited:
  • #31
pbuk said:
You are asking why it is not possible to use things that don't exist? It is difficult to take this seriously.
Pay attention to that: in call of F3 H1 is never called so that both arguments of H1 are equal.
 
  • #32
olgerm said:
Words "function" and "algorithm" have different meaning.
But you have used them interchangably throughout this thread. Furthermore, the halting problem and computation theory in general is only concerned with algorithms, it doesn't say anything about the abstract mathematical definition of a function: every occurence of the word "function" in this thread should be read as being synonymous with "subprogram".

olgerm said:
There is no such function that does not return anything if called with some argument.
A function is a relation that uniquely associates members of one set with members of another set, it is not something that is "called with an argument" or "returns anything". You are again confusing the set theory concept of a function with the computation theory concept of a subprogram (or the slightly different concept of an algorithm).
 
Last edited:
  • #33
So once more back on topic, from your first post:

olgerm said:
I noticed that this proof would not prove that function subprogram (lets call this function subprogram F3) with following properties would not exist:
  • accepts 2 arguments(lets call these x1 and x2).
  • returns false if x1==x2.
  • returns False if x1!=x2 and call x1(x2) stays in infinit loop.
  • returns True if x1!=x2 and call x1(x2) ever returns.

This is not correct: the "standard" proof to the "standard" halting problem also proves that your subprogram F3 cannot exist. Consider the following subprogram:

pseudocode: 
def A(x):
  if F3(A, x):
    while True:
      pass
  return x

If F3(A, 1) returns True then it has determined that A(1) halts, however if F3(A, 1) is True then A(1) enters an infinite loop, a contradiction.

On the other hand if F3(A, 1) returns False then it has determined that A(1) does not halt, however if F3(A, 1) is False then A(1) halts returning 1, a contradiction.
 
  • Like
Likes olgerm
  • #34
SSequence said:
Since there has been some confusion in this thread I feel it is also worth clearing this point. Strictly speaking the answer to your question is "yes". Of course the function F3 exists. In fact, it is a "partial computable function". Even the two argument halt function ##Halt## is a partial computable function.

However, it is clear given the context of question that what you are asking is whether F3 is a "total computable function" or not? The answer to this is no. Same goes for the the ##Halt## function.
I noticed a mistake in terminology in my post#13. I would like to correct it. Sorry there was confusion here on my part. Saying that ##Halt## and ##F3## are "partial computable functions" is not correct. The following lines would all be correct though:
(1) ##Halt## and ##F3## are mathematically well-defined functions (and also in computation theory).
(2) ##Halt## and ##F3## are ##0'##-computable functions. Probably a relevant link:
https://en.wikipedia.org/wiki/Turing_jump
(3) The following set is "computably enumerable" (often call c.e.) but not "computable":
##A=\{Halt(x,x)| x \in \mathbb{N} \}##

Note that, once you look at the definition of both the terms, every "computably enumerable" set can also be shown to be "computable" quite easily. The halting problem shows that the collection of "computably enumerable" sets is strictly larger than those of "computable" sets.
olgerm said:
no function can stay in an infinit loop. There is no such function that does not return anything if called with some argument.
In computation theory, conventions are are slightly different. For example, a "partial computable function" is allowed to be undefined on some inputs. Perhaps this thread might help:
https://cs.stackexchange.com/questions/31981/what-is-a-partially-computable-function

Of course, if one really wants, we can shut-down this definition and use different conventions. However, these are the ones that are standard.

There is a valid question here though. Computation theory is a branch of mathematics. So if somewhere else in other branch of mathematics we read the word "function", how should we interpret it. From p.o.v. of computation theory, one would simply (mentally) replace "function" with "total function" in all such instances.Also, saying that H1 or F3 are not functions is incorrect. They are functions [unless we are looking at some extremely restrictive form of constructive mathematics...... in which the context would definitively have to be mentioned]. What would be correct to say would be that H1 are F3 are not computable functions. You can read my posts about it in post#5, 8, 23. And indeed the reason is that the usage of H1 in definition of F3 is not redundant.
 
Last edited:
  • #35
olgerm said:
You could implement F3 this way using H1.
It's not just that you could; it's that any implementation of F3 must be logically equivalent to the one using H1 that I wrote. And that means that if H1 does not exist, F3 cannot exist either.
 

Similar threads

I Proof of the Halting Problem's Unsolvability
    • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
I Proof that BB(k) grows faster than any computable function
    • Set Theory, Logic, Probability, Statistics
Replies
15
Views
4K
Halting Problem and Turing's Solution
    • Computing and Technology
Replies
9
Views
1K
Busy Beaver Function: Range of BB Sets
    • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
Comp Sci Problem on undecidable problems
    • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
I Proof involving functional graphs and the injective property
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
737
Python Question about a function call with multiple arguments
    • Programming and Computer Science
Replies
26
Views
2K
Is this computability theory proof correct?
    • Programming and Computer Science
Replies
1
Views
1K
MHB Proof 4 Proof Questions w/ Fuzzy Sets, Functions & Bijections
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
A Defining the membership relation in set theory?
    • Set Theory, Logic, Probability, Statistics
Replies
14
Views
4K

Hot Threads

Recent Insights

Back
Top