How is Turing's Solution to the Halting Problem Not Simply "Failure By Design"?

Question

I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer.

Here is my understanding of the Halting Problem:

Let $M$ be the set of all Turing Machines.

Let $i$ be the set of all inputs for all the Turing Machines in $M$.

Let every element in $M$ be an element in $i$.

Let the boolean values $true$ and $false$ be elements in $i$.

Let $h(M,i)$ be a function that returns:

• $true$ if and only if $M(i)$ halts
• $false$ if and only if $M(i)$ does not halt

Let $p(M)$ be a Turing Machine in $M$ that:

• calls $h(M,M)$
• halts if and only if $h(M,M)$ returns $false$
• doesn't halt if and only if $h(M,M)$ returns $true$

What happens when we call $p$ by passing $p$ to itself, $p(p)$?

The part I take issue with is implementing $p(M)$ so that it will not halt when $h(M,M)$ is $true$. My gut understands this approach as follows:

Given a method $h()$ that works, and a method $p()$ designed to break $h()$, when we combine these methods to build a machine, that machine is broken.

I understand proof by contradiction is a valid approach to problem solving in formal logic, but this particular application of proof by contradiction seems flawed somehow.

What am I missing?

Answer 1

In what follows, I'll distinguish a machine $M$ from its description, denoting the description of $M$ by $\langle M\rangle$.

Specification of the halt tester program, $H$

$H$ takes as input a pair $(\langle M\rangle, i)$, where $\langle M\rangle$ is the description of machine $M$, and $i$ is the input required by $M$.

$H$ halts on any input pair $(\langle M\rangle, i)$ and returns the correct answer, namely:

$H(\langle M\rangle, i)$ returns true if and only if $M$ halts on input $i$.

Now, assuming that there is such a machine $H$, we can use $H$ as a subroutine to construct a program $P$ as follows:

Specification of the "perverse" program $P$

$P$ takes as input a description, $\langle M\rangle$, of a machine $M$.

$P$ works correctly on any input $\langle M\rangle$, namely

$P(\langle M\rangle)$ halts if and only if $M$ doesn't halt when given input $\langle M\rangle$.

The key to this argument is that if we can define a machine $H$ that satiffies the specification above, then we can build a machine $P$ that satisfies the second specification.

However, $P$, when given $\langle P\rangle$, exhibits impossible behavior,

$\qquad\qquad\qquad P(\langle P\rangle)$ halts if and only if $P(\langle P\rangle)$ doesn't halt.

So $P$ fails to meet its second requirement on at least one input and consequently it must be the case that $H$ cannot satisfy its requirement, so consequently we cannot make $H$ as specified.

Now $H$ might very well behave as specified on lots of inputs $(\langle M\rangle, i)$, but the point is that no halt tester can be built that works on all possible inputs.

Answer 2

You say:

The part I take issue with is implementing $p(M)$ so that it will not halt when $h(M,M)$ is $true$. My gut understands this approach as follows:

Given a method $h()$ that works, and a method $p()$ designed to break $h()$, when we combine these methods to build a machine, that machine is broken.

The problem is that $p()$ is NOT designed to break $h()$, it is designed to use $h()$ -- and the usage is valid AND works! Except, it doesn't work when the input is $p()$, which proves that it doesn't work for all input.

Which means that $h()$ doesn't exist, at best $hminus()$ exists. It's not important that $p()$ is broken, what is important is that $h()$ doesn't exist.

If someone says they have written $h()$ you know they are mistaken or lying, if they want to work on creating $h()$ they are wasting your money, and so forth.

It establishes boundaries for what can and cannot be decided and the resources needed to do so.

If someone asks the question: can we determine if $p()$ halts given this input? The possible answers to that are: (a) yes — it does, (b) yes — it doesn’t (c) yes —- but we currently don’t know whether it does or doesn’t, and finally (d) no —- it is impossible to prove one way or the other.

Being able to quickly determine if the answer is (c) or (d) can be extremely useful. Remember Halting doesn’t say we can’t prove a specific $p()$ halts, Halting says we can’t have a general solution that will work for any input. Restrict either $p()$ or the input and the answer is quite frequently yes, that’s trivial.

Answer 3

Here is how a logician might approach the problem:

$h(M,i)$ is the general case solution to the Halting Problem by definition.

$(1)$ $h(M, i)$ must be able to determine whether or not $M$ halts for all $M$ ( i.e. an unrestricted set of $M$ ).

$p(M)$ is an element in $M$.

$(2)$ The following statements are equivalent:

• $p(M)$ halts if and only if $h(M,M)$ returns $false$
• $p(M)$ halts if and only if $p(M)$ doesn't halt

$(3)$ Additionally, the following statements are equivalent:

• $p(M)$ does not halt if and only if $h(M,M)$ returns $true$
• $p(M)$ does not halt if and only if $p(M)$ halts

Both $(2)$ and $(3)$ are contradictions.

$h(M,i)$--the general case solution to the Halting Problem--cannot properly determine whether or not $p(M)$ halts, contradicting $(1)$. Therefore, the general case solution for the Halting Problem does not exist.

Answer 4

You shouldn't think about it in terms "brokenness" because there are pleny of perfectly legitimate programs that are designed to run forever, so running forever isn't necessarily "broken" behaviour.

p is the following simple algorithm, assuming that we already have a function h(X,Y) that returns true if machine X halts with input Y and returns false if it doesn't.

function p(M)
    if (h(M,M)) then
        while (true) do
        endwhile;
    return;

Answer 5

There is another proof by contradiction which you might like better, modelled after Berry's paradox. For a Turing machine $T$, let $N(T)$ be the output of the Turing machine when run on an empty tape, interpreted as a number; possibly $N(T)$ is undefined, if the machine never halts. Let $X_n$ be the smallest number which cannot be produced by a Turing machine having at most $n$ states (such a number exists since there are finitely many such Turing machines). Suppose the halting problem were solvable. Then we could construct a Turing machine implementing the following algorithm:

1. Write the binary encoding of $n$ on the tape.
2. Go over all Turing machines having at most $n$ states, and for each of them that halt, calculate the number they compute.
3. Output the smallest number not appearing in step 2, which is $X_n$.

The latter two stages can be implemented using a fixed Turing machine having $C$ states, and the first using an extra $\log_2 n$ states. In total, we obtain a Turing machine having $\log_2 n + C$ states that calculates $X_n$. When $n$ is large enough, we reach a contradiction since $\log_2 n + C \leq n$: on the one hand, $X_n$ shouldn't be computable using a Turing machine having $n$ states; on the other, the machine above computes it using only $\log_2 n + C \leq n$ states.

I heard this proof from Ran Raz.

Answer 6

The point of the halting problem is that it is impossible decide with an algorithm whether a given algorithm halts. Sure, you can give algorithms that will always halt (for all given input). However, you cannot decide this for all algorithms (for example $p$) with one algorithm, hence no algorithm $h$ can exist.

Given $p(p(A)))$, for a given algorithm $A$. If $h$ tells you $A$ halts, then the inner $p$ will not and the outer $p$ will return false . If $M$ does not halt the inner $p$ will not halt, but the outer $p$ will return false. Therefore, h cannot decide whether p will halt.