Given the encoding of a Turing machine, we can determine the number of states it has.

Given the encoding of a Turing machine and an input for that Turing machine, we can determine what are the first 100 configurations of its computation on that input.

In particular, we can build a Turing machine that can simulate the operation of any Turing machine.Given the encoding of a Turing machine, we can determine whether it halts within 1000 steps on any input (or on every input).

CS1104 Main Page

Last Updated 01/05/2000

© L.Heath, 2000