Description
1. (10 Points) Let M1 and M2 be two Turing machines. Consider the following Turing machine:
On input w:
• Step 1: Run M1 on w. If M1 accepts w, then accept.
• Step 2: Run M2 on w. If M2 accepts w, then accept.
What is the language of this Turing Machine? Explain.
2. (15 Points) Let E be an enumerator for a language L with the extra property that it will print
the words in an increasing order of lengths. That is it will never print a word w before a shorter
word u.
Prove that L is decidable.
3. (15 Points) Is the following language decidable1
?
L = {hMi | M = ({1, 2, . . . , 100}, {0, 1}, {0, 1, t}, δ, 1, 2, 3) is a decider}.
1Recall that a TM is formally defined as (Q, Σ, Γ, δ, qstart, qaccept, qreject). A Turing Machine is called a decider if it
halts on every input.
1
4. (20 Points) In the class we showed that the following language is Turing Recognizable. Prove
that it is in fact decidable.
L = {hp(x)i | p(x) is a polynomial with integer coefficeints that has an integer root}.
5. (20 Points) Without using Rice’s theorem (See Problem 5.28 of the textbook) prove that the
following language is not decidable
L = {hMi | L(M) is finite}.
6. (20 Points) You are allowed to use Rice’s theorem (See Problem 5.28 of the textbook) to answer
this question. For each one of the following three languages, either prove that they are decidable,
or prove that they are undecidable.
(a)
Lr = {hMi | L(M) is a regular language}.
(b)
LT R = {hMi | L(M) is a Turing recognizable language}.
(c)
Ld = {hMi | L(M) is a decidable language}.
2