Mathematics

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 Mthat decides L.
a) (15 points) Describe in words how Mworks. 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 Mbe the automaton from Figure 3.8 in Sipser.
Suppose that Mis given an input of 0000. Give the rst 10 congu-
rations that Mwill take.
b) (5 points) Suppose that Mis given an arbitrary input x and
allowed to run, generating the congurations C0, C1, . . .. What is the
largest number of characters by which any Cand Ci+1 can dier?
Why?
Question 4) (20 points) Use dovetailing to show that the language
L= { 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.

Leave a Reply

Your email address will not be published. Required fields are marked *