Halting problem disproof

Question

Introduction

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 counter

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.

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])$. 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:

1. $H(H)$ is not telescopic
2. $H(H)$ is telescopic, but 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 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.

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

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

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.

Answer 1

the original disproof seems not to care what the function $h(f,x)$ or the condition it evaluates to (Halt or no) actually is

This statement looks to me like a misunderstanding. The original proof does "care": see the statement "Assume there exists a function $h(f,x)$, which returns $True$ iff $f(x)$ halts.".

Let the function $r(f,x)$ return $-f(x)$, where $f(x)$ is a function which returns a value.

This is not yet a well-defined definition of $r$. If the intent is to define a mathematical function, you must specify the result of $r$ on all possible inputs; you haven't specified what the value of $r(f,x)$ is when $f(x)$ doesn't return a value. If the intent is to define an algorithm (i.e., a function in some programming language), you must specify the steps the computer takes to compute it. There is no (always-terminating) way for a computer algorithm to check whether $f(x)$ will return or not.

Perhaps you mean that the algorithm $r(f,x)$ is defined by the code "return -$f(x)$". In that case, there is no "where..." clause.

In that case, it appears that $R(f)$ can be defined as the algorithm that executes the code "return -$f([f])$".

I find the definition of "telescopic" unclear. For instance, if I define the function $g$ by $g(x)=7$ for all $x$, is $g(g)$ considered telescopic? Well, $g(g)=7$ and $g(g(g))=7$ and so on, so $g(g)=g(g(g))=\cdots$, so it appears it satisfies the conditions of the definition and can be considered telescopic. Yet I'm unsure whether that is your intent.

I don't understand what is the definition of $H$ in this proof.

I don't understand why it follows that if $H(H)$ is telescopic then $R(R)$ is not telescopic.

I don't understand what you mean by the time complexity of $H(H)$ being $O(1)$. $H(H)$ is a single expression. To use asymptotic notation, normally we have to have a family of problems, with running time a function of the length of the problem input. That doesn't seem relevant here as we don't have a family of problems, we don't have a function, we just have a single expression $H(H)$. The running time to evaluate $H(H)$ is what it is: it is either a fixed constant (if $H(H)$ terminates) or it is infinite (if $H(H)$ doesn't terminate). Asymptotic notation is not applicable here.

---

I haven't tried to check the rest of the argument for errors. One error is enough to invalidate a proof.

In general, if you're not convinced by a proof, rather than trying to construct some other complicated proof that seems analogous to you, it might be a more effective strategy to identify the first statement in the proof that you don't find convincing. If do you find all statements convincing, then presumably you should be convinced by the proof. When you construct a long complicated proof, there is a good chance there is an error in it somewhere, but checking the correctness of proofs is not really the purpose of this site. Our mission is to build up a high-quality archive of knowledge, in the format of questions and answers that will hopefully be helpful to others in the future. If you're the only one to come up with that long complicated proof, then it's not clear how checking that proof in detail would contribute to the mission.

Answer 2

I don't understand your points about telescoping and time complexity, but I don't think I need to.

I see you have defined this program $r(f,x)$ and you have found a case where the program does not halt and there's no way to fix it to make it halt. What I think you have proven is: there is no such program $r(f,x)$ that always halts and returns the negative of whatever $f(x)$ returns.

You could make one that did always halt, but it wouldn't always give the correct answer. Every possible $r$ either gives wrong answers or sometimes doesn't halt.

To connect this to the halting problem, notice that a halting decider always halts. If a program sometimes doesn't halt, then it's not a halting decider. You proved that every possible program-negative-number-maker gives wrong answers or sometimes doesn't halt, and therefore it isn't really a program-negative-number-maker. The same logic shows that every possible halting decider gives wrong answers or sometimes doesn't halt, and therefore it isn't really a halting decider.

See also Rice's theorem which says: "all non-trivial semantic properties of programs are undecidable." Yup, that's right - all of them. There's no way to tell whether a program always returns 42. There's no way to tell whether a program always returns a positive number. Your version isn't quite the same but I think it's the same basic idea.