EECS 376: Foundations of Computer Science
University of Michigan, Fall 2021 Homework 5
Due 8:00pm, October 6
(5% off until 9:59 pm, no credit
... [Show More] after)
Problems marked with P are graded on progress, which means that they are graded subjectively
on the perceived progress toward a solution, rather than solely on correctness.
For bonus questions, we will not provide any insight during office hours or Piazza, and we do not
guarantee anything about the difficulty of these questions.
We strongly encourage you to typeset your solutions in LATEX.
If you collaborated with someone, you must state their name(s). You must write your own solution
for all problems and may not look at any other student’s write-up.
0. If applicable, state the name(s) and uniqname(s) of your collaborator(s).
Solution:
1. Prove or disprove the following statements about Turing reducibility.
(a) If L ≤T L
0
for some language L
0
, then L is decidable.
Solution: This statement is false.
L is always decidable if L ≤T L
0 and L
0
is decidable. However it is not necessarily
decidable when L
0
is undecidable.
If L ≤T L
0
this just means that if there exists a blackbox decider for L
0
then it would
be possible to construct a decider for L.
Assuming we have a blackbox decider for an undecidable language can allow us to
construct a decider for another undecidable language in many cases. That is, in
many cases, an undecidable language is Turing reducible to another undecidable
language.
An example is shown in section notes 4 where we show that LAcc ≤T L∅
(both LAcc
and L∅ are undecidable).
Also note that every language is Turing reducible to itself, even if it is undecidable.
(b) For any decidable language L and an arbitrary language L
0
, L ≤T L
0
Solution: This statement is true. Because L is decidable, there is a TM B that
decides it. Given a black box B0
that decides L
0
, a machine that decides L is
simply. . . B itself.
The point is this: even though a black box that decides L
0
is available, the decider
for L is not required to use it (and does not need to, in this case). [Show Less]