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