8
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ It would help this discussion if you could clarify exactly why you feel that "this particular application seems flawed". Your comments on the answers help a bit, but I still don't see exactly what's troubling you. $\endgroup$ Aug 28, 2014 at 13:49

6 Answers 6

11
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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;
$\endgroup$
10
  • $\begingroup$ While there are pleny of perfectly legitimate programs that are designed to run forever, there are requirements imposed upon this project, as it were. Namely, that it should solve the Halting Problem. p() is designed so that, when combined with h(), the resulting machine will no longer meet the project requirements. Isn't this simply a design flaw? $\endgroup$ Aug 27, 2014 at 11:32
  • 4
    $\begingroup$ No. h() is designed to "meet the project requirements" (i.e., decide the halting problem). We assume that this program exists and works. p() is something that one of your programmers wrote while he was messing about on his lunch break. It's not that it "doesn't meet the project requirements", it's that it's an impossible program: if it doesn't halt, it halts; if it does halt, it doesn't halt. Since the assumption that h() exists and works led to an impossible situation, we are forced to conclude that h() doesn't exist. $\endgroup$ Aug 27, 2014 at 12:20
  • $\begingroup$ Are we saying that p() is an impossible program, or are we saying that p() combined with h()--taken as a whole--is an impossible program? $\endgroup$ Aug 27, 2014 at 12:24
  • $\begingroup$ I guess I can see the rabbit hole we are going down: in order for p() to evaluate p, p must be fed input; why not p? But for p() to evaluate p, p must be feed input; why not... and so on. $\endgroup$ Aug 27, 2014 at 12:27
  • 1
    $\begingroup$ "there are pleny of perfectly legitimate programs that are designed to run forever" -- are you thinking or semi-deciders or things like operating systems? If the latter, this goes beyond the framework of TMs and should hence be left out of beginner questions such as this (imho). $\endgroup$
    – Raphael
    Aug 27, 2014 at 15:11
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Your wording is ambiguous; you need to make clear that "to tell" means "decide with an algorithm" and in what order the quantifiers occur ("for every program exists an algorithm that ..." vs "there is an algorithm that ... for all programs"). $\endgroup$
    – Raphael
    Aug 27, 2014 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.