Prove that a turing machine is neither R.E. nor Co-R.E. Consider the following t

Question

Prove that a turing machine is neither R.E. nor Co-R.E. Consider the following two languages L1 = {(M) | M is a Turing machine and |L(M)| = 1} L2 = {(M) M is a Turing machine and |L(M)| = 2} i.e., L1 is the set of all Turing machines that accept precisely one input string, and L2 is the set of Turing machines that accept precisely two inputs. Problem 1 In this problem you will show that L1 is neither R.E. nor co-R.E. a. Prove that L1 is not R.E. by reduction from the diagonal language D = {(M)|M is a Turing machine such that (M) not in L(M)} b. Prove that L1 is not co-R.E. by reduction from the complement of the diagonal language D. Problem 2 We say that two languages A and B are Turing equivalent if there is both a map reduction from A to B, and a map reduction from B to A. In this problem you will prove that the languages L1 and L2 are Turing equivalent. a. Give a map reduction from L1 to L2 b. Give a map reduction from L2 to L1. Hint: Tile b. direction is the harder one. For this direction, think about how, given a machine M. you might design a machine M? that accepts all strings M does, except the first one. Problem 3 Use the results from problem 1 and problem 2 to prove that tile language L2 is not Turing equivalent to the diagonal language D.

Explanation / Answer

Hints.

If you're trying to figure out some property of a Turing machine and the only thing you can think of is, "Check every input" then it's probably not recursive.

If a language is RE and so is its complement, both are actually recursive (this is a good way of proving that languages aren't RE: for example, the language of pairs ?M,x? such that Turing machine M does not halt on input x is not RE for this reason).

If a Turing machine halts within 100 steps, how much of its input has it seen?

Note that L2 and L3 are subtly different so you can't use the same explanation for both (the answers are actually different).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.