Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My friend claims that one could reduce the number of states of a given turning machine by somehow blowing up the tape alphabet. He does not have any algorithm though. He only has the intuition.

But I say it's not possible. Else one could arbitrarily keep decreasing the states via the same algorithm and arrive at some constant sized machine.

Who is right?

share|cite|improve this question
I think this question is equivalent the following: Let $\mathrm{RE}_n$ be the class of languages accepted by Turing machines with $n$ states and arbitrarily many symbols. For which (if any) $m$ and $n$ is $\mathrm{RE}_m = \mathrm{RE}_n$? I don't know of any results on the languages accepted by Turing machines with a restricted number of states, but then I'm no expert. – Rahul Nov 28 '10 at 11:03
No. I am not looking at a class of languages. For a given language $L(M)$ of a TM $M$, does there exist another TM $M'$ with fewer states such that $L(M) = L(M')$? – user813 Nov 29 '10 at 1:55
up vote 6 down vote accepted

Yes it is possible to reduce the number of states a Turing machine uses to decide a problem $X$ by increasing the number of symbols. However it gets very tricky when you are close to the minimum number of states/symbols needed to solve $X$

Here is a nice survey paper about the efforts to find the minimum number of states and symbols Turing machines need for universality.

"The complexity of small universal Turing machines: A survey" Damien Woods and Turlough Neary, Theoretical Computer Science archive Volume 410 Issue 4-5, February, 2009

share|cite|improve this answer

I think this in the same vein as creating a compression algorithm that will compress any given file, i.e. than we can compress the output again and again, until we reach a single bit that will represent all possible files. Yet, compression algorithms do exist, and they do compress some files.

So, even it the number of states of a given Turing machine is reducible, it does not mean that all Turing machines are reducible, since that would mean that all Turing machines are just different interpretations of one and the same one-state machine.

share|cite|improve this answer
I don't think this line of reasoning is valid in this case. The reason it works for compression is that there are fewer files with a smaller file size, so the pigeonhole principle applies. With Turing machines, if you decrease the number of states but increase the number of symbols, there can be a larger number of possible Turing machines, so it's not obvious that you can't reduce all Turing machines. It's true that you can't reduce them all to just one state, of course. – Rahul Nov 28 '10 at 11:12
If we ignore the alphabet size, and look just at the number of states, the pigeon-hole principle applies again. There might exist algorithms for transforming a n-state Turing machine into an n-1 state Turing machine, but it wont work for all n's – SWeko Nov 28 '10 at 12:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.