COMP 330 - Fall 2020 - Assignment 4   Due: 11:59pm Nov 7 th

COMP 330 - Fall 2020 - Assignment 4

Due: 11:59pm Nov 7 th.

General rules: In solving these questions you may consult books or other available notes, but you need to provide citations in that case. You can discuss high level ideas with each other, but each student must find and write her/his own solution. Copying solutions from any source, com-

pletely or partially, allowing others to copy your work, will not be tolerated, and will be reported to the disciplinary office.

You should upload the pdf file (either typed, or a clear and readable scan) of your solution to mycourses.

1. (10 Points) Let M₁ and M₂ be two Turing machines. Consider the following Turing machine:

On input w:

• • Step 1: Run M₁ on w. If M₁ accepts w, then accept.
  • Step 2: Run M₂ on w. If M₂ 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 decidable^[1]?

L = {hMi | M = ({1,2,...,100},{0,1},{0,1,t},δ,1,2,3) is a decider}.

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 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 )

L_r = {hMi | L(M) is a regular language}.

( b )

L_TR = {hMi | L(M) is a Turing recognizable language}.

( c )

L_d = {hMi | L(M) is a decidable language}.

2