A "State Hierarchy" Theorem for Turing Machines?

Question

In complexity theory, there are time hierarchy theorems for Turing machines that show that for certain functions $f$, there exist problems that cannot be solved by a Turing machine in $o(f(n))$ time.

Is there something equivalent for the number of states in a Turing machine? That is, are there languages for arbitrary $k$ that cannot be decided by a k-state Turing machine?

Thanks!

Answer 1

You can trade the number of states for the size of the alphabet on the tape. More precisely, for any $k$ there is an $N_k$ such that any $k$-symbol Turing machine (no matter how many states it has) can be converted to an equivalent machine with at most $N_k$ states but with a larger alphabet.

This works by allocating a new symbol for each state in the original machine, and simply using a designated square on the tape to remember the original-machine state. We cannot remember this state when we move away from that designated square, but instead of moving the state around on the tape we can use simple loops to shift the contents of the entire rest of the tape to the left or right when the original machine would have moved right or left.

In order to do this, we need $O(k)$ states to implement the shifting, $k$ states to remember what we jsut read when moving from the "read/write" position to the "state" square, and $3k$ states to remember what we're going to do now while moving back out of the state square.

Allowing $O(1)$ states for initialization and cleanup, and we see that $N_k=O(k)$.

(Alternatively, mark the current read/write position with a designated symbol, and duplicate everything such that the machine always remembers which side of the "state" square the read/write position is to be found on).

Answer 2

You can build (IIRC) a 3-state universal Turing machine, which can obviously solve anything solvable. So I think the answer is "no".

There might, however, be some way of relating the time required to the number of states available...

Answer 3

You can convert any TM to a 5-state Turing machine as follows.

Let $Q=\{1,2,...,n\}$ be states of $M$. The new tape alphabet will be $A \cup (A \times Q \times \{0,1\})$.

On the tape, one place will work as "current head", and the challenge is to move the head one position left or right. The number 0 will mean "update the tape and symbol" (simulate one step of $M$), the number 1 will mean "move the head".

Suppose $M'$ is at $(a,q,0)$. Seeing $0$, we change this to $(a',q',1)$. The challenge is now to change this to $a'$ and a neighbouring cell $b$ to $(b,q',0)$.

We do that in steps: move left/right, increase the number at $b$, move back, decrease the number at $a'$. Once the number at $a'$ reaches 0, we change the symbol to $a'$.

This needs 5 states: accept/reject/return left/return right/start. If you can replace rejection with an infinite loop, that will be 4. I think you can get 3 if you put "return left" and "return right" on the tape.

Answer 4

Given the tradeoff between states and symbols, a more meaningful measure of TM complexity along these lines has been $\text{#states} \times \text{#symbols}$ of a universal TM. Here is stuff on that.

But that has more the flavor of an intellectual game based on somewhat arbitrary models of computation, IMHO, and of course, only addresses the model itself as embodied in the UTM. More serious work uses program size given a specific TM model and associated UTM. That's called Kolomogorov Complexity, and has been developed into a beautiful theory of undecidability and complexity by Chaitin especially and others, with surprising relationships to randomness and probability.

Chaitin's popularization Meta Math! is a nice, lightweight intro but with a fair amount of substance, and there are numerous more mathematical books and papers which you can find by searching. Of course there is the Wikipedia article on Kolomogorov Complexity and this and this on one of Chaitin's best-known results, a real number representing the probability that a randomly constructed program will halt in a given TM model or other formalization of computable functions. It's based on the idea of the shortest program in the formalism that produces a given output.