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