In the book The Annotated Turing, Charles Pezold writes:

Because Turing Machines are entirely defined by a Description Number, it might be possible to create a Turing Machine that analyzes these Description Numbers to determine whether a particular machine is satisfactory or unsatisfactory. Turing proves this is not the case. There is no general process to determine whether a a Turing Machine is satisfactory. The only way one Turing Machine can analyze another is to trace through the operation of the machine to determine what it is going to do.

Now I intuitively understand this has something to do with the Halting Problem, but I'm having trouble expressing why this is the case in this situation. (Ie I understood Turing's Paper to be about the impossibility of a general algorithm to solve Diophantine equations in a knowable number of steps).

My question is: How did Turing prove that there is no general process to determine whether a Turing Machine is unsatisfactory?

  • 3
    $\begingroup$ What property must a Turing machine satisfy to be 'satisfactory'? Please give us the context of the quote. $\endgroup$ – Lieuwe Vinkhuijzen Mar 4 '17 at 10:32
  • 1
    $\begingroup$ Turing's paper is available online. You can read it and answer the question yourself. Note that "satisfactory" is what we today call "halting", so I imagine that Turing used an argument similar to one of the modern ones. $\endgroup$ – Yuval Filmus Mar 4 '17 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.