I Question about about halting problem and this particular function

[olgerm]

The most known proof of undecidability of the halting problem is about like that:

#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?

 

[Office_Shredder]

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).

 

[olgerm]

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.

 

[Office_Shredder]

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$!).

 

[SSequence]

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.

 

[olgerm]

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.

 

[pbuk]

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:

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$

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?

 

[SSequence]

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.

 

[olgerm]

$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

$B \implies \neg A$

it is untrue because $B = \left ( D(D2) \text{ returns} \right )$
not that $B = \left ( D2(D2) \text{ returns} \right )$

 

[pbuk]

$(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}$?

$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.

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:

def alwaysHalts(x1):
  return x1

print(F3(alwaysHalts, alwaysHalts)) # False

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.

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:

def sometimesHalts(x):
  return x(x)

print(sometimesHalts(sometimesHalts)) # Infinite recursion.
print(sometimesHalts(x: type(x))

 

[olgerm]

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

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.

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.

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.

 

[pbuk]

it does not exist

Yes it does (this is a pointless argument).

it does not exist

I showed you how to write it in #10; for the avoidance of doubt
[code lang=Python title=pseudocode]
def G(x):
return not x(x)
[/code]

• 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.

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!

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.

 

[SSequence]

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".

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.

 

[PeterDonis]

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:

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.

 

[pbuk]

So back on topic, from your first post:

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:

[code lang=Python title=pseudocode]
def A(x):
if F3(A, x):
while True:
pass
return x
[/code]

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.

 

[SSequence]

Yes, it does, because your function F3 is logically equivalent to this:

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".

 

[PeterDonis]

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.

 

[SSequence]

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.

 

[PeterDonis]

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.

 

[PeterDonis]

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.

 

[PeterDonis]

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.

 

[SSequence]

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.

 

[SSequence]

[code lang=Python title=pseudocode]
def A(x):
if F3(A, x):
while True:
pass
return x
[/code]

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.

 

[PeterDonis]

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.

 

[olgerm]

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

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.

 

[pbuk]

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?

 

[pbuk]

F3 is not same as the Halting function H1.

This is obvious, however it suffers from the same problem as the function H1.

 

[olgerm]

Yes, it does, because your function F3 is logically equivalent to this:

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.

 

[pbuk]

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.

 

[olgerm]

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.

 

[olgerm]

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.

 

[pbuk]

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".

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).

 

[pbuk]

So once more back on topic, from your first post:

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:

[code lang=Python title=pseudocode]
def A(x):
if F3(A, x):
while True:
pass
return x
[/code]

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.

 

[SSequence]

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.

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.

 

[PeterDonis]

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.

 

[PeterDonis]

What would be correct to say would be that H1 are F3 are not computable functions.

Again, this depends on what mathematical domain you are working in. In the domain assumed in the OP to this thread, H1 and F3 do not exist. Since they do not exist, it is meaningless to even ask whether they are functions. Similar remarks apply to "computable".

If you expand your domain to include, for example, "oracles", as in your previous posts, then H1 and F3 can exist in that expanded domain and you can ask questions like whether they are computable or non-computable. But you have to be working in a domain where they exist to begin with to even pose those questions.

 

[SSequence]

Again, this depends on what mathematical domain you are working in. In the domain assumed in the OP to this thread, H1 and F3 do not exist. Since they do not exist, it is meaningless to even ask whether they are functions. Similar remarks apply to "computable".

If you expand your domain to include, for example, "oracles", as in your previous posts, then H1 and F3 can exist in that expanded domain and you can ask questions like whether they are computable or non-computable. But you have to be working in a domain where they exist to begin with to even pose those questions.

OK I will put it this way. In ZFC [and indeed many much much weaker theories that can talk about functions] H1 and F3 are functions. However, they are not computable functions in any of those theories.

It might be possible that there are some strict theories (that are based on constructivism) that can talk about functions but still H1 and F3 are indeed not functions [further, the basic idea of halting problem can still be carried out]. But someone well-versed in this would be more qualified to comment.

 

[PeterDonis]

In ZFC [and indeed many much much weaker theories that can talk about functions] H1 and F3 are functions.

Doesn't the proof referred to in the OP, that H1 does not exist (and similarly for F3 based on follow-up posts), contradict this claim?

 

[SSequence]

Doesn't the proof referred to in the OP, that H1 does not exist (and similarly for F3 based on follow-up posts), contradict this claim?

The proof in the OP shows that:
"There is no computer program computing a (total) function $f:\mathbb{N}^2 \rightarrow \{0,1\}$ such that:
(a) If the program with index $a$ halts on input $b$ then $f(a,b)=1$.
(b) If the program with index $a$ loops forever on input $b$ then $f(a,b)=0$."

Now if we think [for example, based on concerns raised by constructivism] that all the (total) functions $f:\mathbb{N}^2 \rightarrow \{0,1\}$ must necessarily be those that are computed by some computer program then what you wrote would indeed be correct and H1 would not exist.

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

Note that when we say that much of mainstream mathematics is formalized by ZFC , then this also includes results like incompleteness theorems, halting problem etc. That is, they are theorems of ZFC. Of course this debate can go philosophical on "what comes first or not" [and honestly, I am not qualified to comment on this]. Nevertheless, there would be a (finite) proof of these results in ZFC.

For example, we will have an actual predicate $P(x,y)$ in language of set theory such that:
$P(x,y)=Halt(x,y)$ for all $x,y \in \omega$

Similarly:
"$Halt:\mathbb{N}^2 \rightarrow \{0,1\}$ is not a computable function."
would be a theorem of ZFC and many weaker theories.

Of course actually formalizing this requires much more understanding and attention to quite a bit of details (and tbh I don't know the details well at all ..... only the basic idea).

 

[PeterDonis]

Now if we someone thinks [for example, based on concerns raised by constructivism] that all the (total) functions $f:\mathbb{N}^2 \rightarrow \{0,1\}$ must necessarily be those that are computed by some computer program then what you wrote would indeed be correct.

Hm, ok, if we leave aside the proof in the OP for a moment, how do we know that such a total function does exist in ZFC?

 

[SSequence]

Here is one way to think about it. The real numbers are not countable in ZFC. But every real number can be thought of as being associated with a unqiue function from $\mathbb{N}$ to $\{0,1,2,3,4,5,6,7,8,9\}$. And hence also to a function from $\mathbb{N}$ to $\mathbb{N}$.Regarding your specific question in previous post, I will try to do so later (but I don't know the details too well). Nevertheless, I will try to describe based on how much I know (even if its limited).

 

[PeterDonis]

Why do you think that the number of (total) function from $\mathbb{N}$ to $\mathbb{N}$ will be countable in ZFC?

It might not be. But that's really a separate question from the one we're discussing. We are discussing one particular (claimed) total function (or two of them, but we can focus on just H1), which has certain known properties. That set of known properties pins things down to a smaller set of functions than the set of all possible total functions from $\mathbb{N}^2$ to $(0, 1)$. That smaller set might be countable even if the larger one is not.

Regarding your specific question in previous post, I will try to do so later (but I don't know the details too well). Nevertheless, I will try to describe based on how much I know (even if its limited).

Ok.

 

[SSequence]

Regarding the first quote, fair point. The questions may not be the same.

Ok.

If we are thinking about it from a basic perspective then, as I described in previous post, we can write a predicate $P(x,y)$ [in language of set theory ...... useful link: https://mathweb.ucsd.edu/~sbuss/CourseWeb/Math260_2012F2013W/AxiomList.pdf] with two open variables $x,y$ such that:
$P(x,y)=Halt(x,y)$ for all $x,y \in \omega$
It seems to me that firstly we will need to have a convention to encode functions as relations though.

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

If we think from a more indirect perspective (and not the details), then for every model of ZFC the reals numbers $\mathbb{R}$ will necessarily contain all the arithmetic sets [link: https://en.wikipedia.org/wiki/Arithmetical_set]. Note that we are thinking about real numbers as subsets of $\omega$ here. And the arithmetic sets also contain the halting set [and essentially also the halting function using a suitable computable bijection from $\mathbb{N}^2$ to $\mathbb{N}$].Edit: I modified my previous reply, because I felt that it was a bit of over-kill approach (and maybe would distract from main discussion).

 

[PeterDonis]

we can write a predicate $P(x,y)$ [in language of set theory ...... useful link: https://mathweb.ucsd.edu/~sbuss/CourseWeb/Math260_2012F2013W/AxiomList.pdf] with two open variables $x,y$ such that:
$P(x,y)=Halt(x,y)$ for all $x,y \in \omega$
It seems to me that firstly we will need to have a convention to encode functions as relations though.

Functions are easy, they are just sets of ordered pairs, where for each pair the first element is from the domain, and the second element is from the range.

The key part is encoding what Halt actually means in a formula of set theory; that is required in order to express the predicate you describe. You can't just wave your hands and assume that can be done; you have to prove it.

Note that your reference is to first-order set theory, but we can't really express what we need to express in first-order set theory. The kind of formula we are after is something like this:

$$
\exists P \forall x \forall y [ x \in \mathbb{N}, y \in \mathbb{N}: P(x, y) = Halt(x, y)]
$$

To make this a fully well-formed formula we would then have to unpack $Halt(x, y)$ appropriately.

But since this quantifies over a predicate, it is a second-order formula, not a first-order formula. So we can't prove it using just first-order set theory.

 

[SSequence]

$$
\exists P \forall x \forall y [ x \in \mathbb{N}, y \in \mathbb{N}: P(x, y) = Halt(x, y)]
$$

To make this a fully well-formed formula we would then have to unpack $Halt(x, y)$ appropriately.

I am afraid you are incorrect here. The names we assign to predicates are just short-hands for a logical formula. They are not part of the "actual" set theory language. If you look at the link I posted in previous post, several short-hands are already described there. There are no base symbols there except $\in$.

$Halt$ can absolutely be unpacked. However, I don't know the way it is done unfortunately. So I don't think I can help in the detail of that at all. Couple of things that I can say I have written below. Sorry they are definitely imprecise and roughly written, so I am not confident about the precision of what I have written (even if that is how the basic idea goes like).==================From the first line of link in my previous post:
"In mathematical logic, an arithmetical set (or arithmetic set) is a set of natural numbers that can be defined by a formula of first-order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy."

And the arithmetical hierarchy contains the halting set etc. Very roughly, Peano arithmetic quantifies over $\omega$ or $\mathbb{N}$. In ZFC once we have the finite ordinals and $\omega$, we can quantify over it [well sort of ..... formally the quantification is always on universe of sets ..... but we can simulate a quantification over $\omega$].

 

[PeterDonis]

The names we assign to predicates are just short-hands for a logical formula.

Doesn't matter. I'm not saying you can't have predicates in first-order logic. I'm saying you can't quantify over predicates in first-order logic. That's what second-order logic is for.

$Halt$ can absolutely be unpacked.

I'm not saying it can't. I'm just saying that once it's unpacked, we have to actually look to see if the formula can be proved. We can't just assume it.

 

[SSequence]

I will try to describe very roughly little bit I know. To determine halt first we form a predicate $P(a,b,t)$ that describes the state of a program with index $a$ (with input $b$) at a finite time $t$. These variables $a$,$b$,$t$ quantify over natural numbers.

So $P(a,b,t)$ is true iff the program with index $a$ and input $b$ halted at some time $\leq t$. Now we define $Halt(a,b)$ as [note that $a$ and $b$ are open variables in the formula below]:
$\exists i \in \mathbb{N} [P(a,b,i)=1]$.

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

It seems that this is called kleene's T predicate. However, the full details of how it fits into the complete picture (of only using logic) I don't know very well:
https://en.wikipedia.org/wiki/Kleene's_T_predicate

 

[TeethWhitener]

I don’t know if this helps, but here’s how I think about it. The crux of non-computability (and its baby brother undecidability) comes from the encoding of the computational model. Everything falls out of Cantor’s theorem ultimately.

A program/algorithm/computational model is encoded as a finite string, or equivalently, as a natural number. So to use the most famous example, a Turing machine is encoded as an n-tuple (finite n) that is equivalent to a member of the set $\mathbb{N}^n$. Importantly, this encoding is a bijection (an encoder is pretty useless without a decoder). So we have a bijective encoding function from the set of all Turing machines to the set of all n-tuples over the natural numbers:
$$E:{}TM\to\mathbb{N}^n$$
The Turing machine takes a set of tape marks as an input and returns a set of tape marks as output, each of which can be represented as members of $\mathbb{N}$. So the Turing machine is essentially a function on the natural numbers: $$TM:\mathbb{N}\to\mathbb{N}$$
(A decision problem is just an algorithm returning a yes/no response $D:\mathbb{N}\to\{0,1\}$)
However, from Cantor’s theorem, we have that the cardinality of all functions from $\mathbb{N}$ to $\{0,1\}$ is $|2^{\mathbb{N}}|=|\mathbb{R}|$, which is strictly larger than the cardinality of $\mathbb{N}$ (and of course the same result holds for the set of all functions from $\mathbb{N}$ to $\mathbb{N}$). But the cardinality of the set of all Turing machines is $|\mathbb{N}^n|=|\mathbb{N}|$, since the encoding function is a bijection. This means that the set of all functions from $\mathbb{N}$ to $\mathbb{N}$ is strictly larger than the set of all Turing machines. So there must exist functions from $\mathbb{N}$ to $\mathbb{N}$ that are not Turing-computable.

So the halting function clearly exists (as a function from $\mathbb{N}^2$ to $\{0,1\}$, it takes as input an encoded Turing machine and its input), but it is not a member of the pre-image of the encoding function, which means it can’t take itself as an input.

 

[TeethWhitener]

Quick correction: I don’t think the encoding function has to be bijective. It definitely must be injective (every Turing machine has a unique encoding to the natural numbers), but I don’t know if it has to be onto. Regardless, this just means that the set of all Turing machines still has cardinality at most $|\mathbb{N}|$, so the argument still goes through: the halting function cannot be represented as a Turing-equivalent machine and therefore can’t take “itself” as an input (since it cannot be encoded into the natural numbers).

 

[SSequence]

I don’t know if this helps, but here’s how I think about it. The crux of non-computability (and its baby brother undecidability) comes from the encoding of the computational model. Everything falls out of Cantor’s theorem ultimately.

I didn't read the whole post yet. However, I suppose there are few ways diagonalization can be thought of in this context.

For example, think of all total computable functions placed [possibly with repetition] in rows just like in cantor's theorem. So, for example $F_x(y)$ is the output of the $x$-th function in the list when given the input $y$. Then the following function $g:\mathbb{N} \rightarrow \mathbb{N}$ is both total (by definition) and non-computable (due to diagonalization):
$g(x)=F_x(x)+1$But indeed if we are thinking about it from computational perspective, the problem of determining that whether a function computed by a given program is total or is not decidable [in fact, not even $0'$-computable ..... it is $0''$-computable].

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

If we try a similar thing for index of all programs of course it won't (and shouldn't) work. For example, let $\phi_x(y)$ be the output of the program with index $x$ when given the input $y$. Note that output can possibly be undefined.

Now we define a function [that may or may not be defined on some inputs] $h: \mathbb{N} \rightarrow \mathbb{N}$ as:
$h(x)=\phi_x(x)+1$
What this is supposed to mean is that:
(a) We return $h(x)=\phi_x(x)+1$ if $\phi_x(x)$ is well-defined (returns a value).
(b) We return $h(x)$ as undefined if $\phi_x(x)$ is undefined.The resulting function $h$ will have following properties:
(1) It will be undefined on some inputs. That is, it will not be total.
(2) The resulting function will be a "partial computable function".Here one thing to is that the set $\{Halt(x,x)| x \in \mathbb{N}\}$ is not a computable set. Since the set is c.e. (computably enumerable) but not computable, it can be shown without much difficulty that it can't be a co-c.e. set [because a set which is c.e. and co-c.e. at the same time must be computable]. So we can't (computationally) hope to "identify" those points where the function $h$ is undefined [in hope of diagonalizing them].