Dept. of Computer Science Assignment # 2 CSC 463H1 University of Toronto (Due Feb 12, 3:00 pm) Winter 2021
Worth: 15%
1. [20 marks]
Let A be an arbitrary language.
(a) Show that A is semi-decidable if and only if A ≤m AT M . (This, combined with the fact that AT M
is semi-decidable, shows that AT M is complete for the class of semi-decidable problems.)
(b) Show that if A is semi-decidable and A ≤m Ac, then A is decidable.
Solution.
(a) (←−)
Since A ≤m AT M and AT M is semi-decidable, by property of reduction it follows that A is semi-decidable.
(−→)
If A is semi-decidable, by definition there is a TM M such that w ∈ A ⇐⇒ M accepts w. Define
f:Σ∗ → Σ∗
w → ⟨M,w⟩
f is clearly computable. Moreover,
w∈A ⇐⇒ Macceptsw ⇐⇒ ⟨M,w⟩∈ATM.
Hence, A ≤m AT M .
(b) Let f be a computable function witnessing A ≤m Ac, i.e., x ∈ A ⇐⇒ f (x) ∈ Ac. By contraposition, xA ⇐⇒ f(x)Ac,i.e.,x∈Ac ⇐⇒ f(x)∈A,whichprovesAc ≤m A(witnessedbythesame computable function f ).
Since A is semi-decidable and Ac ≤m A, it follows by property of reduction that Ac is semi- decidable, i.e., A ∈ coSD.
Finally, since SD ∩ coSD = D, it follows that A ∈ D. 2. [20 marks]
Let A be an arbitrary language.
(a) Show that there exists a language B such that B m A.
(b) Show that there exists a language C such that A ≤m C and C m A. Solution.
(a) ConsiderthesetS={B|B≤mA}.ForeachB∈S,thereisacomputablefunctionf :Σ∗→Σ∗that witnesses the reduction B ≤m A. Moreover, there is a 1-1 correspondence between B and f , i.e., if there are two different sets B and C such that B ≤m A and C ≤m A, then both the reductions cannot be witnessed by the same function f . Otherwise, for any w ∈ B \ C (assuming without loss of generality that B\C ∅), it follows that f (w) ∈ A (since w ∈ B) and also f (w) A (since w C), a contradiction.
We know that the number of Turing machines is countable. In particular, the number of computable functions is countable. Because of the 1-1 correspondence, it follows that S is countable. But the set of languages over Σ is uncountable. Thus, there exists a language B such thatBisnotinS,i.e.,Bm A.
University of Toronto Department of Computer Science Page 1 of 3
Dept. of Computer Science Assignment # 2 CSC 463H1 University of Toronto (Due Feb 12, 3:00 pm) Winter 2021
(b) Picktwodistinctcharactersa,b∈Σ,anddefineC={ax|x∈A}∪{by|y∈B}.
(If Σ has only one character a, define C = {xx | x ∈ A} ∪ {ayy | y ∈ B}.) Ineithercase,wehaveA≤m C andB≤m C.
But since B m A (by part (a)), it follows that C m A (since otherwise B ≤m A by transitivity of ≤m ).
3. [20 marks]
Show that every infinite semi-decidable language has an infinite decidable subset.
Solution. Since A is semi-decidable, there is an enumerator E that prints the strings of A in some order, say {x0,x1,x2,…}. Inductively define a subset B ⊆ A by declaring that x0 ∈ B, and for j > 0, xj ∈ B if and only if its length is greater than xi for all i < j. By construction, B ⊆ A and is infinite, since A must contain strings of arbitrarily large length if A was infinite.
To show that B is decidable, we modify the enumerator E to construct an enumerator E′ that prints B in lexicographic order. E′ simulates E and prints the first string x0 that E prints. After that point, every time E prints a string xj, E′ compares its length to the last string xi that it itself printed, and prints xj if and only if xj is longer than xi. Clearly, E′ enumerates B lexicographically, and hence B is decidable.
4. [20 marks]
A Turing machine M has a useless state if there is some state q that is never entered on M’s compu- tation beginning on any string w. Let U = {⟨M⟩ | M is a Turing machine with a useless state}. Show that U ∈ coSD \ D.
Solution. Assume, for a contradiction, that U has a decider S. Construct a decider N for AT M as follows:
On input ⟨M,w⟩:
• Construct a TM R on the input alphabet {0, 1, 2} as follows: on input 0, R goes through all non-halting states of M and then enters qaccept; on input 1, R enters qreject; and on input 2, R simply simulates M on w, and if that simulation enters M’s accept state, R enters a new state qA and accepts.
• Run S on input ⟨R⟩. If it accepts, reject; if it rejects, accept!
Note that the only possible useless state of R is the state qA because R uses all the other states on inputs0and1. AndtheonlywayforRtousethestateqA isifM acceptsw. Thus,Rdoesnothavea useless state if and only if M accepts w. On the other hand, N accepts ⟨M,w⟩ if and only if S rejects ⟨R⟩, i.e., R does not have a useless state. Combining the two, we obtain that N accepts ⟨M,w⟩ if and only if M accepts w. In other words, N decides AT M .
To show that U ∈ coSD, we show that Uc ∈ SD by designing a TM N that recognizes Uc as follows: On input ⟨M⟩:
• Make a list of all the states of M
• Repeat the following for i = 1,2,...:
• Generate string si lexicographically
• Append it to the existing strings with a delimiter
• Execute M’s next move on the inputs s1,...,si
• After each computation, grab the state M moved to, and add it to a seen list. • The moment all states of M are seen, halt and accept.
University of Toronto Department of Computer Science Page 2 of 3
Dept. of Computer Science Assignment # 2 CSC 463H1 University of Toronto (Due Feb 12, 3:00 pm) Winter 2021
If M does not have a useless state, if will take finitely many strings to go through all the states of M, and hence N, on input ⟨M⟩, will halt after finitely many steps. But if M has a useless state, N will never halt on input ⟨M⟩. In other words, N recognizes Uc.
University of Toronto Department of Computer Science Page 3 of 3