206 views
0 votes
0 votes
We have considered only Turing machines that have input alphabet $\left\{0,1\right\}$. Suppose that we wanted to assign an integer to all Turing  machines, regardless of their input alphabet. That is not quite possible because while the names of the states or noninput tape symbols are arbitrary, the  particular input symbols matter. For instance, the languages  $\left\{0^{n}1^{n}\mid n\geq 1\right\}$ and $\left\{a^{n}b^{n}\mid n\geq 1\right\}$, while similar in some sense, are not the same language, and they are accepted by different $TM's$. However, suppose that we have an infinite set of symbols, $\left\{a_{1},a_{2},\cdot\cdot\cdot\right\}$ from which all TM input alphabets  are chosen. Show how we could assign an integer to all $TM's$ that had a  finite subset of these symbols as its input alphabet.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
3
admin asked Jul 21, 2019
310 views
Show that the set of Turing-machine codes for TM's that accept all inputs that are palindromes (possibly along with some other inputs) is undecidable.