CSC 363 — Assignment 2
Due Monday, February 25th, 5:00pm
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources
(people, print, electronic) outside the course and lecture notes, that you consulted.
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct but that are hard to understand may not receive full marks. Mark values for each question are contained in the [square brackets].
I will be in my office all Monday afternoon (on the 25th) or you can put the assignment in my mailbox in DH 3008.
1. Prove or disprove each claim below:
(a) If A is decidable and B is decidable, then A ∪ B is decidable. [5]
SOL: This is true, you can directly build a decider for the union.
D(x) = run D_A on x
if D_A accepts x -> accept
if D_A rejects x
run D_B on x
if D_B accepts x -> accept
if D_B rejects x -> reject
(b) If A ∪ B is decidable, then A and B are decidable. [5]
SOL: This is false. Let A = A and B = A ̄ , neither are decidable, but the
TM TM
union is Σ∗ which is decidable.
(c) If A is decidable and B is decidable, then A ∩ B is decidable. [5]
SOL: This is true, you can directly build a decider for the intersection.
D(x) = run D_A on x
if D_A accepts x
run D_B on x
if D_B accepts x -> accept
if D_B rejects x -> reject
if D_A rejects x -> reject
(d) If A ∩ B is decidable, then A and B are decidable. [5]
SOL: This is false. Let A = A and B = A ̄ , neither are decidable, but the
TM TM
intersection is {} which is decidable.
2. Let Σ = {0, 1}. Your friend claims that it is easy to create Turing Machines which accept strings which only contain 0’s, i.e. 0, 00, 000, etc. They then claim, that therefore, all
1
languages which only contain strings made exclusively from 0’s are decidable. Formally prove your friend wrong. [10]
SOL: To prove your friend wrong, show there are unrecognizable languages which only contain strings of 0 (this implies there are undecidable languages). The proof that there are unrecognizable languages with strings made only from 0’s is almost identical to the proof that there are unrecognizable languages. See the Week 4 lecture slides.
3. Let FIN = {M | L(M) is finite}, and recall HP = {M#w | M halts on w}. ̄ ̄
(a) Prove HP ≤m FIN, where HP is the complement of the halting problem. That ̄
is, show there exists a computable function f such that M#w ∈ HP iff f(M#w) ∈ FIN. [5]
SOL:
f(M#w) = on input x, ignore it and run M on w:
. if M accepts → accept
. if M rejects → accept
. if M loops → loop (forced)
Note: f(M#w) accepts an infinite language (Σ∗) when M halts on w, and a finite language (the empty set), when M loops on w.
(b) Prove HP ≤m FIN. That is, show there exists a computable function f such that M#w ∈ HP iff f(M#w) ∈ FIN. [10]
SOL:
Let S be a Turing machines which steps through its input and when it reaches the end of the input string, accepts.
f(M#w) = on input x, run concurrently M on w and S on x:
. if S accepts before M halts → accept
. if M halts before S accepts → reject
Note: f(M#w) accepts an infinite language (Σ∗) when M loops on w, and when M halts on w, f(M#w) accepts a finite language (all strings will length less than n, where n is the number of steps M takes on w).
f(M#w) ∈ FIN ⇔ f(M#w) accepts a finite language ⇔ M halts on w ⇔ M#w ∈ HP
(c) Is FIN decidable? Is it recognizable? Justify your answer. [5]
SOL: From (b) we know FIN is undecidable, from (a) we know FIN is unrecog- nizable (and also undecidable).
2