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?
1
- 1$\begingroup$ Similar post $\endgroup$fade2black– fade2black2017-09-13 11:16:42 +00:00Commented Sep 13, 2017 at 11:16
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
3 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:
- The description of the machine is no longer finite.
- 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– Raphael2017-09-13 17:11:50 +00:00Commented Sep 13, 2017 at 17:11
- $\begingroup$ @Raphael You can "accumulate" the entire input into once cell, and then immediately output the correct answer. $\endgroup$Yuval Filmus– Yuval Filmus2017-09-13 17:19:34 +00:00Commented Sep 13, 2017 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– Raphael2017-09-13 18:52:12 +00:00Commented Sep 13, 2017 at 18:52