Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)?
Intuition tells me not, since you need an infinite number of states to differentiate each symbol. So I think some of the symbols or the transitions caused by the symbols (or some subsets of the transitions) have to be equivalent. So you can actually simulate such machine with a regular TM and a bounded subset of such symbols or transitions.
How could I approach a formal proof of this?
Asked By : zad
Answered By : Ben
No, it would be more powerful. The transition function would no longer be finite, and that buys you a lot of power.
With an infinite alphabet, you can encode any input item from an infinite set in one symbol (although the input set can't be "more infinite" than the alphabet set, e.g. the alphabet would presumably be only countably infinite, so elements of uncountable sets like the real numbers couldn't be represented in one symbol). And likewise for the output.
So you can make a two-state (one initial, one accept) infinite-alphabet-TM with a single transition that moves to the accept state and changes the symbol under the tape head in accordance with the function you're trying to compute. This recipe would allow you to compute any mapping between sets that can be put in a one-to-one correspondence with the alphabet.
So to avoid that degenerate sort of machine being the answer to everything, you'd need to restrict what the transition function can do. An obvious one would be to require the transition function itself to be computable (ordinary TM's transition functions are trivially computable after all, since they're finite). But then you'd be trying to use computable functions to define your model of computable functions.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3533
0 comments:
Post a Comment
Let us know your responses and feedback