The Halting Problem Revisited
Cristian S. Calude · 2012
The Halting Problem Revisited 1 / 10The halting problem for Turing machines cannot be solved by any Turing machine Classical proofs use diagonalisation which seems artificial as the argument: looks like a linguistic trick, does not reveal “the cause ” of the impossibility. The Halting Problem Revisited 2 / 10An information-theoretical argument Assume that: we interest ourselves to (Turing) machines working with natural numbers as inputs and outputs; there exists a halting machine HALT which solves the halting problem for the above class of machines. The Halting Problem Revisited 3 / 10An information-theoretical argument Construct the machine Trouble(N): 1 read a natural N; 2 generate all machines and inputs (T, n) of up to N bits in size; 3 use HALT to remove all pairs (T, n) for which T does not stop on n; 4 run the remaining computations T (n) till they stop; 5 compute the largest value o output by these machines and output 2o + 1. The Halting Problem Revisited 4 / 10Trouble(N) is in trouble 1 Trouble(N) halts for every N. 2 The size in bits of Trouble(N) is about log N plus a constant. 3 For large enough N, Trouble(N) has less than N bits in size. 4 For large enough N, Trouble(N) generates itself at some stage of the computation: by examining the output, we get a contradiction.