I Question about about halting problem and this particular function

[SSequence]

There is something that came to my mind (and I have noticed it for first time). Perhaps someone else may also find it interesting. It can be thought of as a comment to first paragraph from post#48.

I noticed that we can use the function $h:\mathbb{N} \rightarrow \mathbb{N}$ in last post [defined as $h(x)=\phi_x(x)+1$] can be used with one basic modification to show the following (essentially via diagonalization and simulating other programs):
(a) The function from $\mathbb{N}$ to $\mathbb{N}$ that maps $x$ to $Halt(x,x)$ can't be a total computable function.
(b) From (a) we can easily infer that the function $Halt:\mathbb{N}^2 \rightarrow \{0,1\}$ can't be a total computable function.This method via diagonalization (very similar to cantor's theorem) is almost certainly very well-known (but I haven't read it before or seen it mentioned).

 

[olgerm]

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.

Since this is a correct implementation of F3, all other correct implementations of F3 must be logically equivalent to this one.

All correct implementations of F3 must be also logically equivalent to implementations of F3 that use functions that can be "simplified out" from there.
All correct implementations of F3 must be also logically equivalent to this implementation:

def F3(x1, x2):
    if 2+2==3:
        return unneeded_function(0)
    if x1 == x2:
        return False
    else:
        return H1(x1, x2)

but unneeded_function can be simplified out from this definition.

But how does this prove that an implementation of F3 that does not use H1 can not exist? How does this prove that if H1 does not exist, F3 cannot exist either?

 

[pbuk]

But how does this prove that an implementation of F3 that does not use H1 can not exist?

We already have a proof that F3 cannot exist that is independent of its implementation:

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]

One of the direct reasons why $F_3:\mathbb{N}^2 \rightarrow \{0,1\}$ is not computable is because we have:
$Halt \leq_T F_3$
Here $\leq_T$ is the notion of "turing reducibility". This is what is shown in post#8.

What the above inequality (and post#8) implies, in more direct wording, is that $F_3:\mathbb{N}^2 \rightarrow \{0,1\}$ can't be computable. Let's suppose $F_3$ was computable. Then, by definition, it means that we have a program to compute $F_3$. And it can be shown (as in post#8) that if we had a program to compute $F_3$ then we would also have a program to compute $Halt:\mathbb{N}^2 \rightarrow \{0,1\}$. That would imply that $Halt$ is computable, which we already know to be false. Hence our original assumption of $F_3$ being computable must be incorrect.
Edit:
I removed my comment about the idea in previous post being accurate [as an argument that shows $F_3$ is not computable]. Not because I think it is inaccurate (my guess is that it is quite likely to be accurate). But rather because, after some more thought, there are certain aspects that seem somewhat more subtle to me (and I can't fully justify using my personal knowledge, understanding etc.).

However, it seems to me that such concerns might be addressed by recursion theorem [though this is still a guess....]. However, my understanding of that theorem is quite weak. Or maybe I am missing out on something simpler. I don't know for sure yet.

In the case that such concerns can be addressed [and my feeling is that they can .... but I am having some difficulty doing it based on my current understanding/knowledge], then my comments in post#23 would probably apply.

 

[SSequence]

Perhaps I should mention that a similar method to one in post#51 [that can be used to show that $x \mapsto Halt(x,x)$ is non-computable] can also be used to show that $F_3:\mathbb{N}^2 \rightarrow \{0,1\}$ is not computable. I will describe a brief sketch.

We write $\phi_x(y)$ to describe the output of the program of index $x$ when given the input $y$. If the program doesn't halt on given input then $\phi_x(y)$ is undefined. Now we construct a function $f(x):\mathbb{N}^2 \rightarrow \{0,1\}$ as follows:
If $x=0$ then we set $f(x)=0$. If $x \geq 1$ then we define:
$f(x)=\phi_{pre(x)}(x)+1$ --- if $F_3(pre(x),x)=1$
$f(x)=0$ --- if $F_3(pre(x),x)=0$
Above $pre(x)$ is subtraction by $1$ function for natural numbers (returning $0$ on input $0$).

Note that the function $f$ is total (same with $F_3$). Now if $F_3$ was computable then it would mean that there exists a program to compute it. However, if that was the case then there would also be a program to compute the above function $f$. That would mean that $f$ is a total computable function. However, by its construction, the function $f$ is different from every (total) computable function. Therefore we conclude that our assumption of $F_3$ being computable was wrong.

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

Edit:
The above might be a bit difficult to follow if one hasn't seen the sketch for showing that the function, say $K:\mathbb{N} \rightarrow \{0,1\}$, defined as $x \mapsto Halt(x,x)$ is non-computable using the same method as above.

In that case, we construct the function $f:\mathbb{N} \rightarrow \{0,1\}$ [used for showing that $K:\mathbb{N} \rightarrow \{0,1\}$ is not computable] as follows:
$f(x)=\phi_x(x)+1$ --- if $K(x)=1$
$f(x)=0$ --- if $K(x)=0$
Note that the specific value of $f$ that we have set as $0$ in second line of definition isn't particularly important. We could have set the value to $1$, $100$, $20$ etc. and it would make no difference.

Now we can use the similar reasoning as above (in the last paragraph of first half of the post) to conclude that $K:\mathbb{N} \rightarrow \{0,1\}$ isn't computable.