# Halting problem disproof

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

• Note it should be h([f],x) and so on - when a program is used as input data, it's always the program representation that is used. Of course you and I and anyone who understands the halting problem realizes that, but some people don't... Dec 14, 2022 at 14:51
• – D.W.
Dec 15, 2022 at 0:39
• I find this confusing right from the start. let f(x) be an arbitrary piece of code run on the input x. What is f? A function? A piece of code? They are very different things. What is a piece of code run on the input x? A result? A sequence of events occurring in a machine executing the code for f? I gave up at that point. Please use clear definitions of terms. Dec 15, 2022 at 21:50
• I think you are misusing the term "time complexity" but in the way you are using it, I think all halting problem solvers have "constant time complexity" because they do eventually halt. If they do not halt, they are not halting problem solvers. Jan 11 at 11:29

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.

• Thank you for the reply! After reading your comment I realised there is a typo - when I said doesn’t halt I meant does halt. We create the function r which only runs on functions which return a number. This is as r essentially just multiplied the output to a function by -1, which doesn’t work if the function doesn’t halt. This is still correct in the rest of the proof. I should also add that when I said the original proof doesn’t “care”, what I meant was there seems to be no reason in the logic that the condition is halting, instead of anything else. I tried to demonstrate this with r. Oct 21, 2022 at 19:43
• The way that this helps the mission of stack exchange is not by checking my proof - I don’t have a proof or an interesting tidbit of knowledge or something like that. Why this is a useful question is as it asks about some of the seeming contradictions in Turing’s proof by showing how these contradictions might be seen to lead to a breakdown of the original proof. These seeming contradictions are also questions others have had before, however my way of asking makes it harder to answer them; I say if you get out like this then you can do the same to another program which leads to a breakdown. Oct 21, 2022 at 19:52
• @Mercury, it will only help someone else who follows the same thought process as you and comes to think of the same alternative proof. I think a more effective strategy is likely to be to try to identify what step of the standard proof you have doubts about, and ask about that. Trying to construct an analogous proof is too prone to error; if you are not perfect in your understanding of mathematics, it's too likely you'll make mistakes in your analogous proof, and those mistakes might not actually shed any light on your confusions about the original proof.
– D.W.
Oct 21, 2022 at 20:51
• Thank you for editing your answer with the things you spotted! To address them: 1) your assessment for what r and R are is correct. 2) telescopic just means that a function can be expanded into an infinite chain of functions. Your example of g(g) is not telescopic as g(x) does not run a function or take in a function - it just returns 7. This means that g(g) would just take in a string input which is not interpreted as a function, so g(g) just returns 7, and cannot be expanded to g(g(g(…))). h(f,x) on the other hand is basically h(f(x)) so H(H) might be able to be expanded to H(H(H(…))) cont. Oct 25, 2022 at 8:11
• 3) the definition of H is the exact same as in the original proof of the halting problem. 4) I don’t think I said that, I said “if case 1 [H(H) is not telescopic] is true then the function R(R) is also logically not telescopic”. If you are confused about why this is, the answer is that both R(R) and H(H) are defined in a similar way - by “squishing” a function which requires 2 inputs into one which requires only one, and then running the new function on itself to create what I see as essentially an infinite loop. Cont. Oct 25, 2022 at 8:23

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.