COMP 3030 Fall 2019 Homework Assignment 5
due Friday, November 22, 2019, 11:59pm
Must be submitted on Crowdmark, not UM Learn
1. [4 marks] Using a reduction, prove that Equaltm is unrecognizable.
2. Let L = {w | w = 〈M, q〉 where M is a Turing machine and q is a state in M such that:
there is at least one input string w such that M executed on w enters state q}.
Side note: In real-world talk, you can think in terms of finding “dead code” in a program. For a given piece of source
code and a particular line number, is there an input that will make the program execute that line?
(a) [4 marks] Using a reduction, prove that L is undecidable.
(b) [4 marks] Prove that L is recognizable. You should not draw a Turing Machine, just provide a
pseudocode of the algorithm and prove that it recognizes the language.
3. [4 marks] Prove that HALT is unrecognizable.
4. [6 marks] Prove that HALT cannot be reduced to Emptytm.
Warning: It is not enough to define one specific reduction and then show that it won’t work. You have
to prove that no reduction exists.
Hint: Try a proof by contradiction.
5. Questions about closure properties! In all cases, assume that the alphabet is Σ = {0, 1}.
(a) [4 marks] Prove that the set of all decidable languages is closed under intersection.
In other words: if L1, L2 are decidable, then L1 ∩ L2 is decidable.
(b) [6 marks] Prove that the set of all recognizable languages is closed under Kleene star.
In other words: if L is recognizable, then L∗ is recognizable.
(c) [3 marks] Prove that the set of all undecidable languages is not closed under intersection.
In other words: if L1, L2 are undecidable, then L1 ∩ L2 is not necessarily undecidable.
(d) [3 marks] Prove that the set of all unrecognizable languages is not closed under union.
In other words: if L1, L2 are unrecognizable, then L1 ∪ L2 is not necessarily unrecognizable.
6. [5 marks] Prove that the following language is decidable. You should not draw a Turing Machine, just
provide a pseudocode of the algorithm and prove that it decides the language.
VegetaStepstm = {w | w = 〈T 〉 and T is a Turing machine that takes over 9000 steps for every input x ∈ {0, 1}∗}
Clarification: “step” means “transition”
7. [4 marks] Prove: A language L is decidable if and only if L ≤m 0∗1∗.
8. [3 marks] Use Rice’s Theorem to prove that VegetaStringsTM is undecidable.
(See Lecture 25 for the definition of VegetaStringsTM)
1