Class: Theory of computing

Topic: Undecidability: A languages that is not recursively enumerable

Problem:

! Exercise 9.1.4: We have considered only Turing machines that have input alphabet {0, 1). Suppose that we wanted to assign an integer to all Turing ma- chines, regardless of their input alphabet. That is not quite possible because, while the names of the states or noninput tape symbols are arbitrary, the par- ticular input symbols matter. For instance, the languages f0"1" |n 2 1} and { a"bn | n 1), while similar in some sense, are not the same language, and they are accepted by different TM of symbols, {a1, a2,...^ 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.j I's. However, suppose that we have an infinite set