This is a heavily updated question I have asked on this forum previously. I have understood and corrected the earlier errors and mistakes I made, and after doing that it still seems I have a problem. I would also like to state that I am not looking for a different proof of the halting problem, and I am not looking to disprove it, just to determine why my counter falls apart.
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 key idea of my counter argument, is that the original disproof seems not to care what the function $h(f,x)$ or the condition it evaluates to (Halt or no) actually is. Taking advantage of that fact, we can recreate the argument except instead of using the function $h$ we create are own function which we know we know exists. This means if we observe a paradox with our new function which we know can be created, the paradox with $h$ does not mean $h$ can't be created.
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])$. 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(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]))$).
We then have 3 possibilities:
- $H(H)$ is not telescopic
- $H(H)$ is telescopic, but has a time complexity > $O(1)$#
- $H(H)$ is telescopic, and has constant time complexity.
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 real. This is as if $R(R)$ is positive, $R(R)$ should be negative and vice versa. The condition that $r$ runs only on algorithms that do not halt 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, and the input size is not infinite as we assume in case 1 that $R(R) != R(R(R(R(R(...)))))$. In case 1, $h$ is not proved as being impossible as the same paradox can be created with a real function.
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 it loops or not, if $h'$ takes infinite time to compute then we get that $H(H)$ does not halt, but this is not because $h'(H)$ has evaluated to true, but because $h'$ does not evaluate at all because it has a telescoping, so infinite sized, input. This is the same paradox as when we run $R(R)$. $R(R)$ telescopes, so although $R$ will return on all non halting inputs, and so $R$ does always halt, $R$ when run on an infinite chain of inputs will 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.
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.
First of all, thank you for reading my convoluted essay, I appreciate you taking the time to read this and 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.