2
$\begingroup$

This is a largely a question of pedagogy/references, though I may have overlooked some nuance of actual mathematics.

I am planning to introduce the concept of Turing machines and the halting problem to utter novices.

The proofs (or rather proof sketches) of undecidability for the halting problem that I have seen fix a universal Turing machine and vary a program and an input that both reside on the TM's tape. In effect an infinite 0-1 array is formed which is indexed by programs and inputs, with entries indicating whether or not the TM supposedly halts on the corresponding program/input pair. One then employs a diagonal argument.

But it seems more concrete to me to ditch the stored program idiom, let the TM vary instead, and use a TM/input pair for the diagonal argument. It is very easy to produce an explicit enumeration of (binary) TMs, and far less so to detail an encoding scheme for a universal TM's tape that allows one to sensibly distinguish the program from the input (of course I know this can be done, but an existence proof is not a great primary approach for very inexperienced students, I think).

So, are there any references that discuss a proof of the undecidability of the halting problem along these lines? (A little part of me actually wonders whether or not I have missed some trivia that obstruct such a proof, because I haven't seen one.)

Improve this question
$\endgroup$
4
  • $\begingroup$ You might consider the subproblem (I think Turing may have used this at one point, if not in his 1936 paper) of deciding whether, using a sutiable encoding, if machine M halts given the input of machine M. If there were a program H to decide it, a tweaking of H gives a logical contradiction. Gerhard "Ask Me About System Design" Paseman, 2011.09.18 $\endgroup$
    – Gerhard Paseman
    Commented Sep 19, 2011 at 5:35
  • $\begingroup$ @Gerhard: the whole point of my desired approach is that it doesn't rely on existence-type arguments as much. As soon as we start talking about "suitable encodings" I might as well resort to the sketch in the third paragraph of my question. $\endgroup$
    – Steve Huntsman
    Commented Sep 19, 2011 at 14:32
  • $\begingroup$ I am seeing lots of "well you can do it another way instead...". These approaches are all too abstract. The students are not familiar with programming. I am trying an experiment here to see if I can successfully introduce TMs to students that otherwise would never see something like this. I am committed to using an array (and so enumerating either TMs or programs) because I am covering the uncountability of the reals in the same material, and this lets me use the same diagonal hammer twice. Actually, when proving a weak form of Gödel incompleteness it lets me use the same hammer thrice. $\endgroup$
    – Steve Huntsman
    Commented Sep 19, 2011 at 16:47
  • $\begingroup$ I think I see why the approach I was looking for doesn't seem to be taken often. The diagonal argument would require constructing a special TM that "does the opposite" on the halting problem. If we're talking about partial recursive functions this is very simple, and in fact I found a reference that tackles it this way. But if we're trying to be concrete about TMs this construction seems to require more abstraction than dividing tapes into programs and inputs. $\endgroup$
    – Steve Huntsman
    Commented Sep 19, 2011 at 19:38

3 Answers 3

Reset to default
7
$\begingroup$

There is another approach that I find students like. Let $L(n)$ be the length of the shortest program (in some programming language the students know) whose behaviour is to write the number $n$ and stop. Assume there is a procedure that computes $L(n)$. Now write a program that computes $L(1),L(2),\ldots$ in a loop until it finds some $k$ with $L(k)>N$, where $N$ is a constant written into the program, then writes $k$ and stops. By adjusting $N$ to be longer than the length of this program (including the procedure for $L(n)$), you get a contradiction. So $L(n)$ is not computable. From that you can do the halting problem: If you could test whether programs will halt, you could compute $L(n)$ just by trying all halting programs in increasing order of length until you find one that writes $n$ before it halts.

Improve this answer
$\endgroup$
3
$\begingroup$

Although I recognize this is a matter of taste, I do not find it unnatural to fix a TM. I find the proof by contradiction relatively concrete. In that proof structure, the start is: Suppose there exists, for the purposes of contradiction, a TM $T_1$ that determines if any other halts. Then we could construct a TM $T_2$ that accomplishes the impossible. So $T_1$ cannot exist. This is the proof in Hopcroft and Ullman's Formal Languages and their Relation to Automata, pp. 108-9.

Perhaps you would find worthwhile the variant on this proof structure used in Aho and Ullman's Foundations of Computer Science, p. 750. Here they do not use TMs, but rather just programs, calling $T_1$ the "decider" program, reaching the conclusion that no such decider can exist via a "complementer" program. One can present a few wiring diagrams using the decider and complementer programs as black boxes to make the contradiction clear. Not-halting can be equated with infinite loops. If your utter novices are programmers, this approach can be more convincing than an indexed diagonal argument.


        alt text

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Joseph: thanks. I don't find it unnatural to fix a TM either. But I'm sure the students will find it either unnatural or overly abstract. The particular structure of a proof I am looking for allows me to hammer home the same point with precisely the same method two or three times. $\endgroup$
    – Steve Huntsman
    Commented Sep 19, 2011 at 16:50
1
$\begingroup$

The proof sketch on Wikipedia uses a very common method (the same as in Proposition 4.4 of Soare's book) that relies only on universality of the computation system and on closure properties of the class of computable functions. It won't make any mention of Turing machines directly, or any other specific model of computation. This is what I think of as the "usual" approach, which could be only half-jokingly described a "get away from Turing machines as fast as possible". The motivation is that computability theory is the study of computable function, not Turing machines.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The source of my question is wanting something as concrete as possible because of the students. This is too abstract. $\endgroup$
    – Steve Huntsman
    Commented Sep 19, 2011 at 14:28
  • $\begingroup$ @Steve: I understand, that makes sense. $\endgroup$
    – Carl Mummert
    Commented Sep 19, 2011 at 15:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .