## Description

COMP 330 – Assignment 4

You should upload the pdf file (either typed, or a

clear and readable scan) of your solution to mycourses.

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