# Can we reduce the number of states of a Turing Machine?

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?

-
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

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. http://portal.acm.org/citation.cfm?id=1498068

"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

-