CSCC63 Assignment 1
Turing Machines and Reductions
Due 11:59pm, February 12
Warning: For this assignment you may work either alone or in pairs. Your electronic submission of a PDF
to Crowdmark affirms that this assignment is your own work and that of your partner, and no one else’s,
and is also in accordance with the University of Toronto Code of Behaviour on Academic Matters, the Code
of Student Conduct, and the guidelines for avoiding plagiarism in CSCC63. Note that using Google or any
other online resource is considered plagiarism.
1. (5 marks) Describe the Church-Turing thesis in your own words.
2. (25 marks)
(a) (20 marks) Let M2 be the following TM. Suppose that M2 is given an input of $001111, so that
the first configuration given this input is q0$001111. Write the remaining configurations that M2
will take when you run it.
q0start q1 q2 q3 q4
q8q5 q6 q7qaccept
$
→
R
xy→ L
0
→
a,
R
a→ R
z → x,R
x, y → R
1→ x,R
0→ R
z → x,R
0, x, y → R
1→ x,R
1→
L
xy
→
L
1
→
L
x→ z,R$→ R 0, a, y, z → L
1→ y,R
x, y, z → R
1→ y, L
(b) (5 marks) What is the is the largest number of characters by which any two neighbouring config-
urations Ci and Ci+1 can differ for this TM? Why?
3. (10 marks) Use dovetailing to write a recognizer for the language:
L3 =
{〈M〉 ∣∣∃ a TM N, 〈M,N〉 ∈ HALT and 〈N,M〉 ∈ HALT}.
4. (20 marks) Let the language L4 be defined as:
L4 =
{〈MN〉 ∣∣ |L(N)| < |L(M)| <∞}.
Is L4 decidable, recognizable, co-recognizable, or neither? Prove your answer.
5. (10 marks) Let L5 be the language
L5 =
{〈M〉 ∣∣L(M) = (L(M))R},
where LR =
{
xR
∣∣x ∈ L}, and where xR is the reverse of the string x.
Show that ALLTM 6m L5.
1
6. (20 marks)
(a) (10 marks) Consider the function
h(〈M,w〉) =
{
k, M halts on w in exactly k steps,
−1, otherwise.
If we could compute this we could compute HALT , and so we know from class that this function
is not computable – there is no TM that will calculate this function and halt on all inputs.
We can in some sense approximate this function, though: show that there are functions hi(x),
i ∈ N, such that:
• ∀i ∈ N,∀x, hi(x) 6 hi+1(x) 6 h(x), and
• ∀x, lim
i→∞
hi(x) = h(x).
(b) (10 marks) Show that there is no such sequence for the function
h(〈M〉) =
{ |w|, w is the shortest string on which M does not halt,
−1, if no such string exists.
7. (10 marks) Suppose that the languages S1, S2, . . . Sk are pairwise disjoint. That is,
for any i 6= j, Si ∩ Sj = ∅. Suppose further that
⋃
16i6k
Si = Σ
∗ and that each Si is co-recognizable.
Prove that each language Si is decidable.
8. Bonus (10 marks — your mark will be rounded to the nearest multiple of 2.5)
Let the language LB be defined as:{〈M,N,w〉 ∣∣ (〈M,w〉 ∈ HALT ) ∧ (〈N,w〉 ∈ HALT )}.
Prove or disprove: LB 6m LB .
2

欢迎咨询51作业君