Suppose you have a Turing machine, but with a countably infinite alphabet.

How does such a Turing machine differ from an ordinary Turing machine, either in terms of computability or of complexity classes?

Do complexity classes for ordinary Turing machines hold up in such a model?

Edit: quick addendum - it seems obvious that the existence of a countably infinite alphabet leads to uncountably many state transition functions. I'm curious for the answer to both my original question, and to the restriction in which the only transitions allowed are recursive.

  • $\begingroup$ Colors? Turing machines don't have colors. I don't understand what you are asking. Is there some context we are missing? Did you mean states instead of colors? I think someone has asked that before -- have you searched thoroughly on this site? $\endgroup$ – D.W. May 18 '17 at 0:28
  • $\begingroup$ Here's the definition of a Turing machine, in which the term "color" is used synonymously with something like "symbol": mathworld.wolfram.com/TuringMachine.html $\endgroup$ – Mike Battaglia May 18 '17 at 0:31
  • $\begingroup$ Got it. That's not an ideal reference on Turing machines, as it uses non-standard terminology & notation. Most computer scientists probably won't know that terminology. I would suggest studying standard references and textbooks to make sure you know the standard terminology, so you can formulate the question in a way others can understand. Are you asking about what happens if the tape alphabet (often denoted $\Gamma$) is infinite? But the input alphabet ($\Sigma$) remains finite? $\endgroup$ – D.W. May 18 '17 at 0:42
  • $\begingroup$ I'm asking about the instance that the tape alphabet and input alphabet are both countably infinite, but I am curious how it would work if we restrict the input alphabet to be finite. $\endgroup$ – Mike Battaglia May 18 '17 at 0:54

Your model accepts all possible languages over the countably infinite alphabet.

The first step is to convert the input word to a single symbol, in some one-to-one fashion. We can do that since $\bigcup_{n=0}^\infty \aleph_0^n = \aleph_0$. You can then encode your language in the transition function.

More generally, to get a non-trivial model you need to ensure that the description length of the machine is smaller in cardinality than the number of words over the alphabet.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.