# A “State Hierarchy” Theorem for Turing Machines?

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!

-
Do you allow an unlimited number of tape symbols? –  Henning Makholm Apr 25 '12 at 15:56
I hadn't considered this. Let's go with any number of symbols. –  templatetypedef Apr 25 '12 at 15:59
If the number of tape symbols is bounded, then there are finitely many machines for fixed $k$. –  sdcvvc Apr 25 '12 at 16:40

## 4 Answers

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).

-

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.

-
Cool. That's more economic than my construction. –  Henning Makholm Apr 25 '12 at 16:48
With a lot more work, you can reduce the number of states to 2. –  JeffE Apr 25 '12 at 20:26
@JeffE: Interesting. Can you give a reference? –  sdcvvc Apr 25 '12 at 21:01
@adcvvc: I believe this is a double-starred homework exercise in the first edition of Hopcroft and Ullman's automata-thoery textbook. –  JeffE Apr 26 '12 at 3:10

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.

-

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...

-
But having this universal TM just means you can simulate any TM, even if it has a lot of states. It does not directly mean that any decidable language can be decided by a three-state TM. –  templatetypedef Apr 25 '12 at 15:57
@templatetypedef: What do you think it would mean for a TM $A$ to be able to simulate another TM $B$, if $A$ can't decide the language accepted by $B$? –  Tara B Apr 25 '12 at 16:11
@MathematicalOrchid: According to wikipedia, you do recall correctly, and in fact there is even a two-state universal Turing machine with 18 tape symbols. –  Tara B Apr 25 '12 at 16:14
Think about it this way - suppose that $L$ is decidable, so there's a TM $M$ for it. With the three-state TM, I can then decide the language { <M, w> | M accepts w } by just simulating M on w. However, the language { <M, w> | M accepts w } is not the language L. Does that make sense? –  templatetypedef Apr 25 '12 at 16:30
@templatetypedef: Yes. –  Tara B Apr 25 '12 at 18:25