You may work with a single partner, but you will have to write your own
solution. If you do work with a partner, please list both of your names on
your assignment. You are not allowed to discuss the assignment with anyone
other than your partner, the TAs, and the instructor.
Question 1) (5 points) Write out Church’s Thesis in your own words.
Question 2) (30 points)
Let L = {x ∈ {a, b, c}|x = anbncn, n ∈ N}. You will need to write out a
TM M2 that decides L.
a) (15 points) Describe in words how M2 works. That is, use descrip-
tions like “Write a ’#’ and move left” or “Move right until you see a
blank character”.
b) (15 points) Formally describe your TM, using the terminology
from example 3.9 in Sipser M2.
Question 3) (25 points)
a) (20 points) Let M3 be the automaton from Figure 3.8 in Sipser.
Suppose that M3 is given an input of 0000. Give the rst 10 congu-
rations that M3 will take.
b) (5 points) Suppose that M3 is given an arbitrary input x and
allowed to run, generating the congurations C0, C1, . . .. What is the
largest number of characters by which any Ci and Ci+1 can dier?
Why?
Question 4) (20 points) Use dovetailing to show that the language
L4 = { M |M halts on at least one input}
is recognizable.
Question 5) (20 points) Show that any innite recognizable language has
an innite decidable subset.