9
$\begingroup$

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?

  • 0
    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')$?2010-11-29

2 Answers 2

7

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

0

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.

  • 0
    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's2010-11-28