This question already has an answer here:

Can I use an infinite alphabet for the tape in a turing machine?

e.g. with input string as (1, 0)* can I define the symbol 1j as the symbol 1 with j marks on top of it where j in a natural number, to be used on the tape?


marked as duplicate by David Richerby, Community Sep 13 '17 at 13:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Turing machines have a finite tape alphabet.

You can think of a generalization of Turing machines with infinite tape alphabet, but there are two problems:

  1. The description of the machine is no longer finite.
  2. Such a machine can decide any language over $\{0,1\}$ (exercise).

There are ways around it - for example, we might require the rules to be finitely specifiable in some specific form. The resulting model will then be equivalent to Turing machines (in terms of computability).

  • $\begingroup$ Every terminating computation can only use a finite subset of the assumed infinite tape alphabet. Do we get any power by allowing the tape alphabet to grow with runtime or input size? Not sure how to solve non-Turing-decidable languages; am I missing something obvious? $\endgroup$ – Raphael Sep 13 '17 at 17:11
  • $\begingroup$ @Raphael You can "accumulate" the entire input into once cell, and then immediately output the correct answer. $\endgroup$ – Yuval Filmus Sep 13 '17 at 17:19
  • $\begingroup$ Ah, assuming we "hardcode" an infinite transition function, yes. I guess I had a finite representation in mind, which you mention separately. $\endgroup$ – Raphael Sep 13 '17 at 18:52

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