2
$\begingroup$

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?

Improve this question
$\endgroup$
1
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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.