CSCC63 Assignment 1
Turing Machines and Reductions Due 11:59pm, June 09
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 $00111, so that the first configuration given this input is q0$00111. Write the remaining configurations that M2 will take when you run it.
x, y → R 0 → R
q q 1→x,R q
start0 1 2 3 4
q xy → L qaccept q 1 → y, L q 1 → y, R q 5 678
a → R $ → R 0, a, y, z → L x → z, R x, y, z → R (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) Let L3 be the language
L3 = ⟨M⟩ if M accepts any string x ∈ {0,1}∗, then it also accepts 1x .
Prove that HALT 6m L3.
4. (20 marks) Let L4 be the language
L4 =⟨M,N⟩ L(M)=L(N) .
Is L4 decidable, recognizable, co-recognizable, or neither? Prove your answer.
5. (10 marks) Use dovetailing to write a recognizer for the language:
L5 = ⟨M⟩ [∀⟨N,n⟩,N loops on ⟨M,M,…,M⟩] → M accepts ε .
z → x, R 0, x, y → R
浙大学霸代写 加微信 cstutorcs
6. (10 marks) Let L6 be the language
Prove that ALLTM 6m L6.
L6 = ⟨M⟩ |L(M)| = |L(M)| ,
7. (10 marks) Prove that L4 6m ALLT M , where L4 is the language defined in question 4.
8. (10 marks) Let L8 be any language that is recognizable but not co-recognizable. Show that there exists a co-recognizable language C8 ⊆ L8 such that |C8| = ∞.
Hint: Use the fact that a language is recognizable iff it has an enumerator.
9. Bonus (10 marks — your mark will be rounded to the nearest multiple of 2.5) Let the language LB be defined as:
⟨M⟩ |L(M)| < ∞ . Prove or disprove: LB 6m DECIDABLE.
Recall the definition of DECIDABLE from week 4:
DECIDABLE = ⟨M⟩ L(M) is decidable .
程序代写 CS代考 加微信: cstutorcs