• 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