An argument against the logic of the halting problem proof

Question

Introduction

When reading a proof of the Halting Problem, something felt off with the way that the halting machine is fed into itself. It feels like there is an infinite chain of halting machines, and so the logic breaks down. This feeling seems like it is a common one, described in other posts like this: Alternative conditions for deciding the halting problem , but i feel like the answer given leads to other significant problems. I have tried to show why I think this answer doesn't work. I would also like to state that I don't believe that my "counter-proof" is correct, but I would like to know why it is wrong.

The original proof

let $f(x)$ be an arbitrary piece of code run on the input $x$. The program $f$ has an encoded representation, e.g in binary, which we denote as $[f]$.
Assume there exists a function $h(f,x)$, which returns $True$ iff $f(x)$ halts. We must then be able to create the composite function $ h'(f)$ which just runs $h(f,[f])$.
We can then create the final function $H(f)$, which can be represented in pseudocode as:

if h'(f):
 Loop
else: 
 return 

To summarise, $H(f)$ will loop if $f([f])$ doesn't, and will not loop if $f([f])$ does.
From the function $H(f)$, we can create a paradox by running $H(H)$. This is as if $H(H)$ loops, then $h'(H)$ must have shown that $H(H)$ did not loop, which is the opposite of out assumption. Likewise if $H(H)$ does not loop, then $h'(H)$ must have shown that $H(H)$ did loop, and paradox. Hence, the function $h(f,x)$ cannot exist.

The counter

For the counter we still use the same functions as in the original proof, e.g $h$, $H$, and $h'$ are the same as in the original proog.

Setup

Let the function $r(f,x)$ return $-f(x)$, where $f(x)$ is a function which returns a value. We can then create the function $R(f)$ which is equal to $r(f,[f])$. An example of using this function would be: $f(x) = 3x$, $[f] = 12$ ($[f]$ is just an example of the encoding of the function), so $R(f) = -(3*12) = -36$. Now I introduce a new definition, telescopic. If a function can be expanded into a infinite tower of functions we call it telescopic, e.g if $H(H) = (H(H(H)) = H(H(H(H(...))))$ then $H(H)$ is telescopic (I have expanded $H$ slightly here for convenience. with the expansion, $H(f)$ is just shown as $H(f([f]))$). A more easy to understand analogy for a telescopic function would be $\sum_{n=1}^{\infty} 1/2^n$, which can be expanded to $1/2 + 1/4 + 1/8 ....$ but also has a definite value of 1. We then have 3 possibilities:

1. $H(H)$ is not telescopic
2. $H(H)$ is telescopic, but $H(f)$ has a time complexity > $O(1)$
3. $H(H)$ is telescopic, and has constant time complexity.

Case 1

If case 1 is true, then the function $R(R)$ is also logically not telescopic. That means we have the same paradox for a function, $r$, which is can be proven to exist. This is as if $R(R)$ is positive, $R(R)$ should have returned a negative and vice versa. The condition that $r$ runs only on algorithms that do not halt, which was part of our assumption for $r$, is not violated. This is because if an algorithm returns a value (so does not halt), the output can be multiplied by -1, which is what $r$ does. This means that for all inputs of $r$, which by definition do not halt, $r$ does not halt. This is the same for $R$. Because of this, $R(R)$ must not violate the condition as $R$ does not halt. We also don't avoid the problem by saying that $R(R)$ has an infinite input size, as we assume in case 1 that $R(R) != R(R(R(R(R(...)))))$. In case 1, $h$ the original proof doesn't work as we can see the same paradox can be created with a real function. This means that if $h$ could exist, we could see the paradox in the original proof, so the presence of the paradox does not imply that $h$ does not exist.

Case 2

If case 2 is true, then the function $H(H)$ telescopes. This means that the function $H(H)$ has an infinite sized input. Because the pseudocode of $H$ just checks if $h'$ returns false to decide if $H$ loops or not, if $h'$ takes infinite time to compute there is an issue. We get the paradox described in the original proof that $H(H)$ does not halt, but this is not because $h'(H)$ has evaluated to true ($h'(H)$ has evaluated its input as halting), but because $h'$ does not evaluate at all! This is because it has a telescoping, so infinite sized, input, and because of it having a non constant time complexity, then it must take infinite time. This is the same paradox as when we run $R(R)$. $R(R)$ telescopes (because $H(H)$ does), so because $R$ will return on all non halting inputs (which are the only valid inputs), $R$ does always halt. This then means $R$ when run on an infinite chain of inputs will not halt, even though the chain is made up of halting functions; an infinite chain of halting functions does not necessarily halt. Because we can create a paradox in the possible function $r$ the same as the function $H$, the paradox for $H$ does not prove that $H$ does not exist - non-termination is not the same as a paradox.

Case 3

If case 3 is true, then because $H(H)$ has an infinite input does not matter; $H$ will still evaluate at some point. In this case, the paradox holds. The reason that even though in case 2 a function which can compute for any input is unable to compute a given input, is as the given input is essentially infinity, which is seen by analogy through $r$. The input being infinity does not matter in case 3, as $h$ takes constant time. The only problem is that for $h$ to compute at always the same pace, $h$ cannot actually read or use the program. A given program which prints "Hello world" 1 time, and then has a while true loop would be evaluated as fast as the same program which prints "Hello world" 3 times. If $h$ knows if a program will halt, it should also know where it halts, or what causes it to halt, so $h$ should identify that the while loop causes it to not halt. The program of "Hello world" and a while loop could be represented as an array, where 1 is the while loop and 0 is a print, the first example could be represented as [0,1]. The second example would be [0,0,0,1]. Any binary array could be represented as a sequence of hello worlds and while loops, but $h$ would be able to determine the existence of a 1 in any of the arrays with constant time, which I do not believe is possible.

Conclusion

Thank you for reading, if you see a mistake please let me know. What I hope I have shown is the following: best case scenario, where my argument in case 3 is incorrect, the halting problem proof seems to only disprove the existence of a function $h$ which acts like case 3. A function $h$ which determines if the input function halts in $O(n)$ or $O(logn)$ or any other time complexity is, on the other hand, valid. On the other hand, even if my argument in case 3 is correct, the exact same conclusion exists where $h$ cannot exist. Have I made a mistake in my logic somewhere? Its possible my case 2 and 3 arguments are incorrect but I cannot work out where I have gone wrong.

Answer 1

Thanks for the clarifications. I believe I've understood your argument so here are a couple of suggestions as to why Turing's argument still holds up despite your counter arguments.

i) While it may indeed feel as though there is an infinite series in Turing's proof, i.e. if $H(H)$ loops then it doesn't and if it doesn't then it does etc. I don't think that this is the right way to think about it. The form of the argument is that if there is a halting function then we can form $H(H)$ which must either loop or halt. We show that either of these possibilities involves a contradiction and hence there is no halting function. I know that you're aware of this, but I think that the point is that it follows that the series $H(H(H...(H)))$ can't even get started, i.e. it doesn't make sense to even consider whether the $H$ series telescopes or not, i.e. whether $H(H)=H(H(H))=H(H(H(H)))=...$, even with a very loose interpretation of the equals sign such as 'the same thing happens', given that it's been shown at the first step that $H(H)$ is contradictory.

ii) Secondly, if I understand you right, your overarching point is that if $H(H)$ (or its expansion) involves a contradiction then it seems that the same thing must be true of $R(R)$ as it has the same form. If so, we know that $R(R)$ is not contradictory and so $H(H)$ cannot be contradictory either. I don't think that this works, however, for example, the sentence

A) This sentence is false

does not have a truth value and is in some sense contradictory, but this doesn't imply that there is a similar problem with a similar sentence of the same form such as

B) This sentence contains exactly two words

(which just happens to be false of course).

What this illustrates is that the property of containing exactly two words is not problematic and that an algorithm can be devised to test it for all sentences, but this does not hold for the property of being true, even though formally these might both be represented by $T(x)$, i.e. $x$ is True or $x$ contains exactly Two words.

Does that help?