Is it Possible for Turing Machines to Solve the Halting Problem?


Home / Is it Possible for Turing Machines to Solve the Halting Problem?

Back to the Diagonal for the Halting Problem: a Mathematician’s Proof

Another, more mathematical, proof that the Halting Problem cannot be solved is another application of Cantor’s “diagonalization” technique. (Cantor created this technique to prove that there are different “sizes” of infinity.)

Diagonal Halting Problem: Image by Mike DeHaan

Any Turing machine’s instructions can be encoded as a string of symbols from a finite “alphabet.” This alphabet can, in turn, be encoded as numbers. Modern computers use ASCII, EBCDIC or other codes to represent letters, digits and special characters, and a similar process can be applied to a TM’s instructions.

Since each different TM has its own unique set of instructions, every numeric encoding of the TM will be a unique number. By a similar process, the input and output strings can be encoded as numbers as well.

  • Let a number ‘i’ be the code for a TM. Let the set S = {i} be the ordered set that lists every encoding for every TM. Since each ‘i’ is a number, the set S can be sorted in numeric order. The set S is an infinite set: there is no limit to the number of instructions for a Turing machine, so long as it is not an infinitely long list of instructions.
  • Let ‘j’ be the number encoding an input for a TM. In some cases, the value for ‘j’ might be found in S. Again, the ‘j’ values form an ordered set. Again, there is an infinite number of finite values for ‘j’.
  • Let HPM be the Turing machine that is supposed to solve the Halting Problem.

Use the set S = {i} from above. Run the HPM machine on the TM corresponding to ‘i’, simulating that TM running with the input string with the value ‘i’. As the HPM predicts whether each TM would halt or not, it builds a table as shown in the diagram above. ‘H’ indicates “will halt”, and ‘N’ indicates “will not halt”. (The machines are listed down the left column as “i #1”, “i #2”, and so on. The inputs are across the top row, also “i #1”, “i #2”, and so on.)

At the same time, the HPM adds a row specifying the behaviour of a new TM, to be known as DM, the “different” Turing machine which will have the encoding number ‘d’. The DM’s behaviour is the opposite of what the ‘i’ TM does when that TM has ‘i’ as its input; DM halts if the TM would not, and does not halt if the TM would halt.

What will HPM predict that the DM would do when it processes the input encoded by ‘d’? If the HPM predicts the DM will halt, then it must construct the DM such that it will not halt. Conversely, if the HPM predicts “will not halt”, then it must construct the DM to halt.

Since we had specified that the set S={i} is the set of all Turing machines, a formal proof would ensure that the value ‘d’ is already included in set S. This again proves that the Halting Problem cannot be solved for arbitrary Turing machines.


Leave a Comment