Turing machine configuration and computation history

Question

These are a series of questions about Turing machines.

First, are the number of a given Turing machine configurations (state + tape) countable? Secondly, given that a computation history is a sequence of configurations, are the number of possible computation histories for a given Turing machine also countable?

My intuition on this question is that since configurations have to be finite (I think), then a configuration can be lexicographically ordered and are therefore countable. Computation histories also have to be finite (I think) so are also countable.

Thanks.

Answer 1

Yes. The number of states of a Turing machine are countable (finite in fact), and since the number of arrangements of symbols (which are of finite variety) on the tape are also countable, the cartesian product of these two sets will also be countable. Note: the cartesian product is an upper bound on the number of possible configurations, some combinations of state and tape will be inaccessible.

As to your next question, are the number of computational histories countable, the answer is yes, since the histories, as you point out, are a finite number of steps. As a result, you can list them by listing all histories that can be achieved in one step from all strings of length one, and then all histories that can be achieved in two steps from all strings of length one, and then all histories that can be achieve in one step from strings of length 2, and so on. You probably saw this with proof that the rationals are countable, by zigzagging along the infinite square of pairs.