EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 6 1 Acceptance
The diagonalization argument provides us with the fact that there are undecidable languages – a major revelation when our goal is to understand what is and is not computable. However, the diagonalization argument is unsatisfying because it is only existential. It does not tell us if a specific language is undecidable. To identify a specific language as undecidable, we will apply a different argument.
The problem of acceptance is a fundamental problem in our definition of computation which only has three outcomes for any input: acceptance, rejection, and looping. If we could decide if a Turing machine M would accept an input x, our understanding of Turing machines would be greatly expanded. To put it in language we have seen before, it would be good if we could decide the language
Copyright By PowCoder代写 加微信 powcoder
LACC = {⟨M ⟩, x : M (x) accepts}.
It turns out that this language is undecidable, i.e. there is no Turing machine M∗ which satisfies
the following properties:
• If M accepts x, then M∗ accepts (⟨M⟩,x),
• If M rejects or loops on x, then M∗ rejects (⟨M⟩,x).
We can show that LACC is undecidable by contradiction.
Suppose for the sake of contradiction that LACC is decidable. Let A decide LACC. Then we can define a new program B which takes as input ⟨M⟩, runs A(⟨M⟩,⟨M⟩), returns the opposite of what A(⟨M⟩,⟨M⟩) returns.
We can now examine what happens what happens when we run M on ⟨M⟩ – remember that ⟨M⟩ is just a bit string, so it is perfectly fine to run M on it.
There are two cases:
• M accepts ⟨M⟩. In this case, A(⟨M⟩,⟨M⟩) accepts and B rejects ⟨M⟩.
• M does not accept ⟨M⟩. In this case, A(⟨M⟩,⟨M⟩) rejects and B accepts ⟨M⟩.
Finally, we ask what if B = M i.e. we want to know what happens if we run B on ⟨B⟩. Then we have
• B accepts ⟨B⟩. In this case, A(⟨B⟩, ⟨B⟩) accepts and B rejects ⟨B⟩ (we state this more weakly as B does not accept ⟨B⟩ to make the point of the proof more obvious).
• B does not accept ⟨B⟩. In this case, A(⟨B⟩, ⟨B⟩) rejects and B accepts ⟨B⟩.
Thus, B accepts ⟨B⟩ if and only if B does not accept ⟨B⟩ but recall that B can only perform one of accept, reject, and loop on any given input – this includes ⟨B⟩! This is the contradiction we seek to show that LACC is undecidable.
2 Turing Reductions
A Turing reduction is a method of converting a problem into another problem, so that a solution to the second problem can also be used to solve the first problem. If we can reduce problem A to problem B, then solving A cannot be harder than solving problem B. This idea is formalized by the notion of Turing reducibility.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 6 Definition 2.1. Language A is Turing reducible to language B, written A ≤T B, if there exists a
program M that decides A using a black-box that decides B. Fact 2.2. If A ≤T B and B is decidable, then A is also decidable.
This fact is intuitive and gives us a method for proving certain problems are decidable.
Fact 2.3. If A ≤T B and A is undecidable, then B is undecidable.
The above fact gives us a strategy for proving the undecidability of a language L. We already know several undecidable languages. If we can reduce any undecidable language to the language L, then L must be undecidable too.
Definition 2.4. For a language L, the complement of the language, L is defined as L={x∈Σ∗ |x∈/L}.
Claim 2.5. For a language L, if its complement L is undecidable, then L is undecidable.
Proof. We will show this by reduction. Explicitly we will show that L ≤T L. To do this we will
construct a Turing machine M which decides L using a black box M′ which decides L.
M = “On input x.
1. Run M ′ on input x.
2. If M ′ accepts, reject.
3. If M ′ rejects, accept.”
Because M′ is a decider, it will always halt, and this means M will always halt as well. By negating the behavior of M′, every string which is accepted by M will be rejected by M′ and vice versa. This ensures that L(M) is the complement of L(M′).
Now, having shown that L ≤T L, using fact 2.3 (see above) we can conclude that because L is undecidable, then L is undecidable.
Notational Note: We write ⟨x⟩ to say that we are expressing x in terms of the symbols from the input alphabet, which is frequently bits. Therefore, ⟨5⟩ would be the same as writing 1012. Angled brackets are frequently used when expressing inputs to Turing Machines or as elements of languages. One benefit of this notation is to standardize the form of the input and to limit the size of the input alphabet. Angled brackets are also used for inputs other than integers, such as machine code or graphs.
Example 2.6. Let
Claim 2.7. L∅ is undecidable.
L∅ ={⟨M⟩|M isaprogramandL(M)=∅}.
Proof. We will prove the claim by showing that LACC ≤T L∅. This is enough, because L∅ is decidable if and only if L∅ is decidable. We first assume L∅ is decidable and may use a black box E which decides it to construct a new program A which decides LACC. The program A is constructed as follows
A = “On input (⟨M⟩,x).
1. Construct the following machine M′.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022
M′ = “On input w.
1. If w ̸= x, reject.
2. Ifw=x,RunM oninputxandaccept ifM does.”
Discussion Notes 6
Run E on ⟨M′⟩.
If E accepts, accept. If E rejects, reject.”
M accepts x ⇒ M′ accepts x ⇒ E accepts ⟨M′⟩ ⇒ A accepts (⟨M⟩,x).
M does not accept x ⇒ M′ does not accept any w ⇒ E rejects ⟨M′⟩ ⇒ A rejects (⟨M⟩,x).
Thus A decides LACC. Note that while M′ is not guaranteed to halt, A is, because A does not actually run M′, it runs E which is guaranteed to halt as it is defined as a decider for L∅. This shows a Turing reduction from LACC to L∅. Since we know LACC to be undecidable, L∅ must be undecidable as well. This in turn means that L∅ is also undecidable.
Example 2.8. Now, let
LEQ = {(⟨M1⟩, ⟨M2⟩) | M1 and M2 are Turing machines and L(M1) = L(M2)}.
Claim 2.9. LEQ is undecidable.
Proof. We will show a reduction from L∅ to LEQ to show that L∅ ≤T LEQ. We begin by assuming that LEQ is decidable and that we have access to a black box Q which decides it. We want to construct another Turing machine E which decides L∅.
E = “On input ⟨M⟩.
1. Construct the following machine M′.
M′ = “On input w.
1. Ignore input w and reject.”
Run Q on (⟨M⟩, ⟨M′⟩). If Q accepts, accept.
If Q rejects, reject.”
M ∈ L∅ ⇒ Q accepts (⟨M⟩,⟨M′⟩) ⇒ E accepts ⟨M⟩ M ∈/ L∅ ⇒ Q rejects (⟨M⟩,⟨M′⟩) ⇒ E rejects ⟨M⟩
We can discover if a Turing machine M ever accepts any input by comparing it to a Turing machine M′ which accepts nothing using Q. If Q says they are equivalent, then L(M) = ∅ and if Q says they are not equivalent then L(M) ̸= ∅.
Example 2.10. Let
LHALT<376 = {(⟨M ⟩, x) | M halts on x after running for less than 376 steps}.
Claim 2.11. LHALT<376 is decidable.
Proof. We will construct a decider H that will decide the language LHALT<376. In other words, H will accept all (⟨M⟩,x) pairs for which M halts on x in less than 376 steps, and H will reject all (⟨M⟩,x) pairs for which M does not halts on x in less than 376 steps (either M halts on x in at least 376 steps, or M loops on x).
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 6 H = “On input (⟨M⟩,x).
Run M on x one step at a time, maintaining a counter variable for the number of steps taken.
If counter variable becomes equal to 376, reject. Else, accept.”
M halts on x in less than 376 steps ⇒ counter variable never reaches 376 ⇒ H accepts (⟨M⟩,x). M does not halt on x in less than 376 steps ⇒ counter variable will reach 376 ⇒ H rejects (⟨M ⟩, x). Therefore, H is a decider for LHALT<376 and since we were able to write a decider for LHALT<376,
then LHALT<376 is decidable.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com