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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityCan 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?
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:
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).