Halting problem logic must be wrong

Question

I think that I have found an issue with the proof of the halting problem, which would cause the entire proof to be invalid.

To ensure I understand, here is Turing's proof of the halting problem being unsolvable.

Proof:

Assume the function $h(x,y)$ determines whether the function $y(x)$ halts on input x, $h(x,y)$ returns True, or 1 if $y(x)$ halts, otherwise it returns False or 0.

Given that the function $h(x,y)$ exists, it must be possible to create a new function, $h'(x)$, which is just $h(x,x)$. In essence, $h'(x)$ determines if the program $x()$ halts when run with itself (encoded in the form of a number).

If $h'(x)$ also exists, then again, a new function $H(x)$ can be created. $H(x)$ in pseudo code is:

Def H(x) 

    If h'(x) == True: 

Loop forever 

    Otherwise: 

Return() 

Now when $H$ is run with itself as an input – $H(H)$ - a paradox is created:

If $H(H)$ will halt, then $H$ run with itself as an input must loop, but that is the original statement

Otherwise if $H(H)$ loops, then $H$ run on itself must halt, which is a contradiction.

Hence $H(x)$ cannot exist, and by extension $h(x)$ cannot exist

Disproof of the proof:

If we assume that the logic in Turing's proof is correct, then we can do this:

Assume the function $l(x,y)$ determines whether $y(x)$ takes more than n, where n is any number, seconds to compute.

Symmetrically to $h(x,y)$ going to $h'(x)$, $l'(x)$ can also be created from $l(x,y)$, where $l'(x)$ = $l(x,x)$.

Finally, exactly the same as in Turing's proof, $L(x)$ can also exist. $L(x)$ will take more than n seconds to compute if $l'(x)$ returns False, and otherwise will take less than n seconds. $L(x)$ does the opposite of $x(x)$.

If $L(x)$ does exist, then $L(L)$ can be run, and results in a paradox the same way that $H(H)$ does.

But the function $l(x,y)$ is possible to create, by simply timing the function $y(x)$. It may be that some adjustments are needed to fix the way $l(x,y)$ works, e.g there is an inherent time associated with the function so you need to subtract a number, but the function should work.

Edit: Because it is confusing as to exactly what $l(x,y)$ is, I should clarify. What the function $l(x,y)$ is is completely irrelevant to whether the proof works. I chose the steps taken or the time taken because it is similar to the original problem, but an easy function might be something like if the first character of x and y are both in the first half of the alphabet. That would still work with the proof.

Not only this, but the logic can be extended to any meta-program, and because most programs could be divided into 2 programs, the same way that $x^2 + 8x + 16$ can be divided into $f(g(x))$ where $f(x) = x^2$ and $g(x) = x + 4$. Turing's proof, if correct, would also prove that any program is not able to be created, which is evidently false, hence the proof must be false. Is this incorrect?

Answer 1

Your analysis of $L(L)$ is not complete.

Indeed, if we assume $L(L)$ loops this implies that $L(L)$ runs in less that $n$ steps, thus $L(L)$ does not loop. Hence our assumption $L(L)$ loops is false. We conclude $L(L)$ must halt. Now if we assume $L(L)$ halts in $<n$ steps, we again get a contradiction (because $L(L)$ loops). Thus $L(L)$ can not halt in $<n$ steps.

Our results is that $L(L)$ halts in $\geq n$ steps. This is entirely consistent with the definition of $L$. Math is not yet broken.

Answer 2

Using "seconds" is not very well defined, so I'll use the usual "steps" instead.

The typical strategy creating a machine for $l$ is to have it simulate $y(x)$ for up to $n$ steps. If the simulation finishes, then it returns true, otherwise it returns false. If you try to diagonalize against this in the same way as the halting problem, you then get:

L(x) =
  if l(L,x)
  then <take more than n steps>
  else halt

This does not work, though. The way that $l$ works takes steps (or time, if you prefer) itself. In fact, simulation of one step takes more than one step, generally (it could just waste $n$ steps, too). So what happens is that $l(x,L)$ simulates $L(x)$ (which runs $l(x,L)$ ...) for $n$ steps. By doing this, it has used more than $n$ steps, so $L$ has, too, and the logic can no longer do anything to use fewer than $n$ steps, because halting immediately still results in a running time of more than $n$ steps.

Incidentally, it still doesn't work if you try to make it more like the halting problem: can a machine decide $l(x,y)$ in fewer than $n$ steps? If you try to diagonalize, then you can't rule out the possibility that the machine for $l$ takes $n-1$ steps to decide $L(L)$ fails, which ensures that $L(L)$ takes $n$ or more steps. The difference is that you can approximate $n$ very closely by a smaller finite number. But no halting computation, no matter how lengthy, approximates not-halting this way, so that just one or two more steps tips over into not-halting.

This doesn't mean that a machine can decide in fewer than $n$ steps if arbitrary other machines complete in fewer than $n$ steps. but it means that the diagonal argument doesn't work to rule it out.

Answer 3

If $l'(x)$ returns false (meaning $x(x)$ does not halt within $n$ seconds) - by running $x(x)$ for $n$ seconds and observing whether it halted - then it necessarily takes more than $n$ seconds to do so.

It's impossible to make a program that runs $l'(x)$ and then halts in less than $n$ seconds if $l'(x)$ returns false, because $l'(x)$ already takes more than $n$ seconds, and the computer which runs this program is not equipped with a time machine.

Your program $L(anything)$ always takes longer than $n$ seconds.

If you had a time machine you might be able to make this work, but then again, if you had a time machine you could also solve Turing's halting problem and become world-famous.

Answer 4

In Turing's proof, $H$ is a function that is obviously computable if $h$ (The putative halting decider function) is computable. The fact that $H$ causes a halting decider to "trip up" is a fundamental aspect of the proof – but conversely, that $H$ uses a putative halting decider is a fundamental aspect of the proof. You do not create the same paradox with arbitrary other functions.

Importantly, Turing's proof of the undecidability of the Halting problem is a proof by contradiction. He demonstrated a situation where the assumption of an universal halting decider does not have a correct answer. If you intend to use the same proof to demonstrate other functions are uncomputable – or as in your case, that the proof itself is flawed and that the Church-Turing thesis is wrong in that there exist intuitively computable functions that cannot be represented by Turing Machines – you must preserve the contradiction.

For a very simple example to contrast with the Halting problem plugged in the same proof frame, let $fastHalt(M)$ determining whether the Turing Machine $M$ immediately halts when run on an empty tape. (This is a special case of your function $l$, incidentally)

Now, $fastHalt$ is intuitively computable and hence there is a Turing Machine that is capable of it. If we create a function $F$ that uses $fastHalt$ similarly to Turing's proof, do we get a contradiction? As pseudocode:

def F(x):
    if fastHalt(x):
        loop forever
    else:
        halt

Is there a contradiction? Only if $fastHalt(F) = \mathsf{TRUE}$ . In that case, $F(F)$ would indeed loop forever, so we can conclude that $fastHalt(F) = \mathsf{FALSE}$ which makes sense, given $F$ cannot be represented as an immediately halting Turing Machine.

Let us fix an $n$ and return to your original function: $l'(x) = \mathsf{TRUE}$ if $x$ takes more than $n$ steps (preferable in analysis over the more chaos-dependent seconds!) to compute before halting or diverging, $\mathsf{FALSE}$ otherwise. Thereby you get this program:

def L(x):
    if l'(x):  //program finishes slow or never
        loop forever
    else:  //program finishes fast
        halt

. Does $L(L)$ force a contradiction? No: if $l'(L) = \mathsf{TRUE}$ this is entirely consistent with the outcome of the computation not halting. If $l`(L) = \mathsf{FALSE}$, this is likewise consistent with the outcome of the computation halting. It gets more interesting if you reverse the logic:

def L'(x):
    if NOT l'(x):  //program finishes fast
        loop forever
    else:  //program finishes slow or never
        halt

This gets us closer to the type of contradiction Turing's proof uses, but falls short of disproving the existence of $l'$: similarly to $fastHalt$, the outcome of $l'(L) = \mathsf{FALSE}$ ($L'(L')$ taking $n$ or fewer steps to compute) is the only case that creates a contradiction, while the outcome where $l'(L') = \mathsf{TRUE}$ creates no contradiction. In essence, what your example proves is the impossibility of a decider that determines whether a Turing Machine halts in $n$ or fewer steps without itself requiring more than $n$ steps to compute.

For one final demonstration, let's try something that doesn't use machines's running time at all and instead does something more tangible. Let $sign(M) = \mathsf{TRUE}$ iff $M$ halts with a single $1$ on the tape when $M$ is run on an empty tape.

Can we spin $sign(M)$ into a contradiction? Let's try:

def S(x):
    if sign(x):
        replace the 1 on the tape with a 0
        halt
    else:
        output 1 on the tape
        halt

Does running $S(S)$ on the tape create a contradiction similarly to Turing's halting proof? Turns out it does! If $sign(S)$ is $\mathsf{TRUE}$, $S(S)$ should halt with a $1$ on the tape, but the $1$ is replaced by a $0$. if $sign(S)$ is $\mathsf{FALSE}$, $S(S)$ should end without a $1$ on a tape but $1$ is output before halting. It follows that $sign(M)$ is not computable – a result that should not surprise a reader familiar with Rice's theorem.

Answer 5

Your proof of the halting problem is missing an essential assumption, which may be confusing you: it is essential to assume that $h$ always halts, i.e., that $h(x, y)$ does not have to run $x(y)$ in order to return. If you remove this assumption, the proof no longer works. If you can find the exact spot and reason that the proof breaks if you remove this assumption, I expect you'll also see why your modifications don't work.