Other proofs


next up previous contents
Next: What is computation? The Turing machine
Up: The halting problem
Previous: A short proof
Back: to main list of student notes

Other proofs

All the proofs I've seen work in a similar way, by reductio ad absurdum. They assume a termination-testing program can exist, show that if it does, then a contradiction always arises, and therefore conclude the initial assumption to be false. In most cases, the contradiction is a program that stops if and only if it doesn't stop.

What Machines can and cannot do by Nievergelt and Farrer, Computing Surveys volume 4 number 2, June 1972. Available as AI photocopy N 21. Their proof has the same structure as in Strachey's letter, but the termination tester is passed the index number for a program rather than the program itself.

Incomputability by Allison and Hoare, from Computing Surveys volume 4 number 3, September 1972. Available as AI photocopy H136.


next up previous contents
Next: What is computation? The Turing machine
Up: The halting problem
Previous: A short proof
Back: to main list of student notes



Jocelyn Ireson-Paine
Wed Feb 14 23:47:23 GMT 1996