EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7 1 Recognizability and Unrecognizability
Definition 1.1. A language L is recognizable if there exists a program R such that for all x ∈ L, R accepts x, and for all x ∈/ L, R does not accept x (i.e., it rejects or loops). The program R that satisfies these requirements is called a recognizer for L.
Theorem 1.2. If L ⊆ Σ⋆ is a language such that both L and L are recognizable, then L is decidable. Proof. Let R and R′ be recognizers for L and L, respectively. We construct a program D that, on
Copyright By PowCoder代写 加微信 powcoder
input x ∈ Σ⋆, does the following:
runRonxandR′ onxinparallel if R accepts, then accept
if R′ accepts, then reject
SinceL∩L=∅andL∪L=Σ⋆,thenallstringsinΣ⋆ areeitherinLorL,butnotboth. Ifx∈L, then R will eventually accept, so D will accept. If x ∈/ L, then R′ will eventually accept, so D will reject. Therefore, D decides L, so L is decidable.
It is not possible for both R and R′ to accept x, or else x ∈ L ∩ L = ∅, which is a contradiction. It is also not possible for neither R nor R′ to accept, or else x ∈/ L∪L = Σ⋆, which is also a contradiction. Therefore, exactly one of R or R′ will accept, so D will necessarily halt and return exactly one accept/reject decision.
Corollary 1.3. If L ⊆ Σ⋆ is undecidable yet recognizable, then L is unrecognizable.
Proof. Let L be an undecidable language. The contrapositive of Theorem 1.2 states that either L
or L is unrecognizable. Thus, if L is recognizable, it must be the case that L is unrecognizable.
By Corollary 1.3, in order to prove that a language is unrecognizable, it sufficies to prove that
it is undecidable and its complement is recognizable.
Example 1.4. LHALT = {(⟨M ⟩, x) : M loops on x} is unrecognizable.
Proof. Recall that LHALT is undecidable by reduction from LACC. We show that LHALT is recog- nizable. Construct the program R that, on input (⟨M⟩,x), does the following:
R(⟨M ⟩, x) : run M on x and once it finishes, accept
If (⟨M⟩,x) ∈ LHALT, then M runs on x for a finite number of steps, so R will eventually accept. If (⟨M⟩,x) ∈/ LHALT, then R will loop forever, so in particular, it will not accept. Thus, R recognizes LHALT, so LHALT is recognizable. By Corollary 1.3, we conclude that LHALT is unrecognizable.
Example 1.5. L∅ is unrecognizable.
Proof. Recall the definition of L∅ and its complement:
L∅ ={⟨M⟩:L(M)=∅} L∅ ={⟨M⟩:L(M)̸=∅}
As shown in Section Notes 4, L∅ is undecidable by composing the following two Turing reductions: LACC ≤T L∅ and L∅ ≤T L∅.
For all i ∈ N, let wi be the ith element of some listing of the elements of Σ⋆ (we know this listing exists because Σ⋆ is countably infinite). Consider the following program R that, when given a Turing machine description ⟨M⟩ as input, does the following:
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022
for i = 1,2,…
for j = 1,2,…,i
run one step of the execution of M on wj if M accepts wj, then accept
In words, R is capable of maintaining separate executions of M on all input strings in Σ⋆ by using a powerful technique called dovetailing, which works as follows:
• wheni=1,RrunsthefirststepofM onw1;
• wheni=2,RrunsthesecondstepofM onw1 andthefirststepofM ofw2;
• ontheithiterationoftheouterloopforanyi∈N,Rrunsthe(i−j+1)thstepofM onwj
for all j from 1 to i.
Dovetailing ensures that for all w ∈ Σ⋆, if M eventually halts on w, then R is theoretically able to run M on w until M reaches the accepting or rejecting state – indeed, this will occur in a finite number of steps. By analogy, dovetailing is similar to the technique used to prove that Q, the set of all rational numbers, is countable.
We claim that R recognizes L∅. In particular, there are two cases:
• If ⟨M⟩ ∈ L∅, then there exists some string w ∈ Σ⋆ such that M accepts w. By the argument above, R is guaranteed to run M on this w to completion within a finite number of steps, so at the latest, R will accept when M accepts w. Since R does not reject before M finishes running on w, then if R halts earlier, it must have also accepted.
• If ⟨M⟩ ∈/ L∅, then L(M) = ∅, so M will not accept any inputs. This means that R will not accept, since the only way it can accept is by finding an input that M accepts. Since R does not accept, R must reject or loop.
As a side note, we know that if M doesn’t accept any input x, then R will loop on M because it will keep running M on new inputs (since Σ∗ is infinite).
Therefore, by Corollary 1.3, we conclude that L∅ is unrecognizable.
2 Semantic Properties
Definition 2.1 (Semantic Property). A semantic property P is a set of languages related to program behavior. Wesaythatalanguage L∈P. LP :={⟨M⟩:L(M)∈P}isthesetofall Turing machines whose language satisfies P.
Example 2.2. A good example of a semantic property is P∞ = {L ⊆ Σ∗ : |L| is infinite} because this set refers to a characteristic of languages. The language corresponding to this property is:
LP∞ = {⟨M⟩ : |L(M)| is infinite}
Discussion Notes 7
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7
Example 2.3. An example of a language with no corresponding semantic property is: L30-STATES = {⟨M⟩ : M has 30 states}
L30-STATES makes no mention of the languages of the Turing machines, so it is not LP for any semantic property P. In fact, L30-STATES corresponds to what is known as a syntactic property, because it refers to the implementation of Turing machines and not their outputs.
Definition 2.4 (Trivial Semantic Property). A semantic property P is trivial if either all recog- nizable languages satisfy it or all recognizable languages do not satisfy it. A semantic property P is nontrivial if there exist two recognizable languages L and L′ such that L ∈ P and L′ ̸∈ P. Equiv- alently, P is nontrivial if there exist two machines M and M′ such that ⟨M⟩ ∈ LP and ⟨M′⟩ ̸∈ LP – just let M be a recognizer for L and M′ be a recognizer for L′.
3 Rice’s Theorem
Rice’s Theorem allows us to classify a broad set of languages as undecidable without having to write a full-fledged Turing reduction. This is because the Turing reduction is “baked” into the proof of Rice’s Theorem.
Theorem 3.1 (Rice’s Theorem). If a semantic property P is nontrivial, then LP is undecidable. Claim 3.2 (Complement of Rice’s Theorem). If a semantic property P is trivial, then LP is decid-
The proof of Rice’s Theorem and its complement can be found in the “Proving Rice’s Theorem” section below.
Using Rice’s Theorem, we can prove that certain languages are undecidable (or decidable) much more easily than could be done with a Turing reduction. The next section shows some applications of Rice’s Theorem.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7 4 Applications of Rice’s Theorem
4.1 Proving Undecidability with Rice’s Theorem
Let L be a language that we wish to prove is undecidable using Rice’s Theorem. We must do the following:
1. Find a semantic property P such that L = LP. 2. Show P is nontrivial.
(a) Find a recognizable language L1 such that L1 ∈ P.
(b) Find a different recognizable language L2 such that L2 ̸∈ P.
3. Conclude that L is undecidable by citing Rice’s Theorem. 4.2 Examples
Example 4.1. L = {⟨M⟩ : M accepts all strings of length less than 376}.
DefineS376 :={x∈Σ∗ :|x|<376}andletP={L⊆Σ∗ :S376 ⊆L}. Then,bythefollowing
chain of equivalences, L = LP.
⟨M⟩ ∈ L ⇐⇒ ∀s ∈ S376,M(s) accepts ⇐⇒ S376 ⊆ L(M)
⇐⇒ L(M)∈P ⇐⇒ ⟨M⟩∈LP
Furthermore, P is nontrivial: Σ∗ ∈ P because S376 ⊆ Σ∗ and ∅ ̸∈ P because ε ̸∈ ∅ (any string of size less than or equal to 376 would suffice for this purpose). Both are recognizable languages. Therefore, by Rice’s Theorem, L is undecidable.
Example 4.2. LDEC = {⟨M⟩ : L(M) is decidable}.
Let P = {L ⊆ Σ∗ : L is decidable}. Then, by the following chain of equivalences, L = LP.
⟨M⟩∈LDEC ⇐⇒ ⇐⇒ ⇐⇒
L(M ) is decidable L(M)∈P ⟨M⟩∈LP
Furthermore, P is nontrivial: Σ∗ ∈ P because Σ∗ is decidable and LACC ̸∈ P because LACC is not decidable. Both are recognizable languages. Therefore, by Rice’s Theorem, L is undecidable.
Example 4.3. LΣ∗ = {⟨M⟩ : M accepts all inputs}.
Let P = {Σ∗}, the set containing Σ∗. Then, by the following chain of equivalences, LΣ∗ = LP.
⟨M⟩∈LΣ∗ ⇐⇒L(M)=Σ∗ ⇐⇒ L(M)∈P ⇐⇒ ⟨M⟩∈LP
Furthermore, P is nontrivial: Σ∗ ∈ P and ∅ ̸∈ P are both recognizable languages. Therefore, LΣ∗ is undecidable by Rice’s Theorem.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7 4.3 Non-Examples
There are some languages whose undecidability cannot be proven using Rice’s Theorem. Neverthe- less, we can always resort to Turing reductions to prove undecidability.
Example 4.4. Lprime = {⟨M⟩ : M has a prime number of states}
We cannot establish whether or not Lprime is undecidable using Rice’s Theorem because the
number of states in a Turing machine is inherently a syntactic property, not a semantic property.
Example 4.5. Ldollar = {⟨M ⟩ : on input “101111000”, M outputs $ at some point on its tape}. This language refers to a property of a Turing machine’s execution and transition function as
opposed to its language.
Example 4.6. LACC = {(⟨M ⟩, x) : M accepts x}.
Although we know from lecture that LACC is undecidable, we cannot establish this fact using
Rice’s Theorem because the “input” to the language is not of the proper format (an element of the language is a machine-string tuple) instead of just a machine.
4.4 Proving Decidability with Rice’s Theorem
Let L be a language that we wish to prove is decidable using Rice’s Theorem. Similar, to how undecidability is proven using Rice’s Theorem, we must do the following:
1. Find a semantic property P such that L = LP.
2. Show that P is trivial.
3. Conclude that L is decidable by citing Rice’s Theorem.
4.5 Examples
Example 4.7. Let L = {⟨M⟩ : L(M) ⊆ Σ∗}. Show L is decidable by applying Rice’s Theorem.
Solution: Observe that L = {⟨M⟩ : L(M) ⊆ Σ∗}. All languages (not just the recognizable languages) are a subset of Σ∗, so every machine should be a part of this set.
What we need to do is construct a P such that LP is the set of all machines. If we take P to bethesetofalllanguagesU,thenweshouldhaveLP ={⟨M⟩:L(M)∈U}. ToshowLP =L
⟨M⟩∈L ⇐⇒ L(M)⊆Σ∗ ⇐⇒ L(M)∈U ⇐⇒ ⟨M⟩∈LP.
Then we need to show P is trivial. Every language (not just the recognizable languages) is an element U, so all recognizable languages satisfy (or are contained in) P.
Then by Rice’s Theorem, L is decidable.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7 5 Proving Rice’s Theorem
In this section, we will prove a simpler version of Rice’s Theorem, and then we will prove Rice’s Theorem in full generality.
We will begin with an example of an undecidable language that we have already seen, and then show that the Turing reduction used for that language can be generalized in order to classify many languages as undecidable all at once.
5.1 Weak Rice’s Theorem
Weak Rice’s theorem is not a commonly used terminology. Indeed, if you were to search for Weak Rice’s theorem, you would not find any reference for it. What we call “Weak Rice’s theorem” is a specification of Rice’s theorem in which a semantic property contains exactly one language. We have only called this theorem Weak Rice’s theorem to emphasize that this theorem can be generalized to Rice’s theorem.
Definition 5.1. Let A be a language, then:
LA ={⟨M⟩:L(M)=A}
In words, LA is the set of Turing Machines whose language is exactly A.
Theorem 5.2 (Weak Rice’s Theorem). If A is a recognizable language, then LA is undecidable.
This is an amazing result – since there are infinitely many recognizable languages A, we have just found an infinite class of undecidable languages!
5.2 An instructive example
We begin by giving an instructive example from which we can generalize the reduction to Weak Rice’s Theorem.
Claim 5.3. LOnlyOnes = {x ∈ {0, 1}∗ : x consists only of 1’s} is decidable.
We will show that it is decidable now by constructing a decider that checks if x contains 0-s:
D always halts since it makes one pass through a finite string. Now we must prove that D is a decider for LOnlyOnes:
• x∈LOnlyOnes =⇒ xconsistsofonly1’s =⇒ noxi =0 =⇒ Daccepts
• x ̸∈ LOnlyOnes =⇒ x contains at least one 0 =⇒ some xi = 0 =⇒ D rejects
Definition 5.4. LTuringOnlyOnes = {⟨M⟩ : L(M) = LOnlyOnes}, which is the set of Turing Machines whose language is LOnlyOnes.
D = On input (x) :
1: Let xi be ith character in x 2: for xi ∈ x do
3: if xi = 0 then reject
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7 Claim 5.5. LTuringOnlyOnes is undecidable
Proof. We can show that LTuringOnlyOnes is undecidable via a Turing Reduction from LACC. Let T be a blackbox decider for LTuringOnlyOnes and let D be our decider from above for LOnlyOnes. Define a decider A for LACC as follows:
A = On input (⟨M⟩,x) :
1: Construct a machine M′ as follows:
2: Run T on input ⟨M′⟩, and then output the same
M′ = “on input ⟨w⟩:
1: Run M on x
2: if M accepts x then, run D on w and output the same 3: else reject
Since T is a decider, A necessarily halts. Therefore it remains to show that A is a decider for LACC :
• (⟨M⟩,x) ∈ LACC =⇒ M accepts x =⇒ M′ accepts all strings in LOnlyOnes and rejects all strings not in LOnlyOnes =⇒ T(⟨M′⟩) accepts =⇒ A accepts
• (⟨M⟩,x) ̸∈ LACC =⇒ M rejects or loops on x =⇒ M′ rejects or loops on all strings in LOnlyOnes =⇒ T(⟨M′⟩) rejects =⇒ A rejects
Thus, we showed that LACC ≤T LTuringOnlyOnes. However, notice that the only connection to the actual language we were reducing from, LTuringOnlyOnes = {⟨M⟩ : L(M) = LOnlyOnes}, was the decider (and therefore recognizer) D for LOnlyOnes and the decider T for LTuringOnlyOnes. We will show that this same Turing reduction can be used to show that any language in the same form as LTuringOnlyOnes is undecidable.
5.3 Proof of Weak Rice’s Theorem
Notice that LTuringOnlyOnes follows this form with A = LOnlyOnes. Because our prior proof did not use any special characteristics of LOnlyOnes other than its decider, we can basically copy the proof and have it hold for any recognizable A ̸= ∅.
Proof of Weak Rice’s Theorem. We show that LA is undecidable via a Turing Reduction from LACC. Assume that A ̸= ∅ (we have previously shown that L∅ is undecidable, so we do not need to consider it here). Let T be a blackbox decider for LA and let R be our recognizer for A. Define a decider D for LACC:
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7
D = On input (⟨M⟩,x):
1: Construct a machine M′ as follows:
2: Run T on input ⟨M′⟩, and then output the same
M′ = “on input ⟨w⟩:
1: Run M on x
2: if M accepts x then, run R on w and output the same 3: else reject
Since T is a decider, D necessarily halts. We now show that D is a decider for LACC :
• (⟨M⟩,x) ∈ LACC =⇒ M accepts x =⇒ M′ accepts all strings in A and rejects or loops on
all strings not in A =⇒ T(⟨M′⟩) accepts =⇒ D accepts
• (⟨M⟩,x) ̸∈ LACC =⇒ M rejects or loops on x =⇒ M′ rejects or loops on all strings in
A =⇒ T (⟨M ′ ⟩) rejects1 =⇒ D rejects
However, having a recognizer R for our language A is an essential part of our Turing reduction above. What happens when A isn’t recognizable?
This is a good exercise to see if you have understood these (relatively abstract) definitions. I encourage you all to think about why this is true before looking at the proof below.
Claim 5.6. If A is unrecognizable, then LA is decidable.
Proof. The key realization is that LA is empty. By the definition of recognizability, L(M) = A =⇒ M recognizes A. Therefore, if A is unrecognizable, then for any Turing Machine M, L(M) ̸= A. Thus, LA = {⟨M⟩ : L(M) = A} = ∅. This language is decided by a machine that immediately rejects.
We have showed that LA is undecidable if and only if A is recognizable, but we can further gen- eralize this result to the full statement of Rice’s Theorem. Instead of only talking about languages of the form {⟨M⟩ : L(M) = A}, we will classify languages of the form {⟨M⟩ : L(M) ∈ P}, where P is some set of languages, instead of just a single language A.
5.4 Proof of Rice’s Theorem and its complement
We begin with the proof of the complement of Rice’s theorem, then provide the proof of Rice’s theorem. The proof of Rice’s theorem is very similar to the proof of Weak Rice’s theorem.
Proof of Complement of Rice’s Theorem. Suppose that P is trivial. Then there are two possibili- ties, either all recognizable languages are in P, or all recognizable languages are not in P.
• If L ∈ P for all recognizable languages L, then every Turing Machine M will be in LP. This is because any language of a machine L(M) is recognizable (since M recognizes L(M)). Thus for any Turing Machine M, L(M) ∈ P, which means that M ∈ LP. Thus, if all for all LP = Σ∗. (This does not mean that P = Σ∗, think about why).
1This is where the assumption that A ̸= ∅ comes into play. There must be at least one string in A so that M′ rejects it, causing L(M′) ̸= A and T(⟨M′⟩) to reject.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7 • If L ̸∈ P for all recognizable languages L, then LP = ∅. This is true by similar reasoning as
above: for any Turing Machine M, L(M) ∈/ P, which means that M ∈/ LP.
We can verify that Σ∗ and ∅ are both decidable by constructing a machine that accepts on all
inputs or rejects on all inputs, respectively.
Proof of Rice’s Theorem. Let P be a nontrivial semantic property such that ∅ ̸∈ P (we can make this assumption without loss of generality: P is nontrivial if and only if P is nontrivial, so if we had ∅ ∈ P, swap P with P). By definition of nontrivial, there exists a machine R such that L(R) ∈ P. We will show the reduction LACC ≤T LP by constructing a decider D for LACC using a black box T for LP.
D = On input (⟨M⟩,x)):
1: Construct a machine M′ as follows:
2: Run T on input ⟨M′⟩, and then output the same
M′ = “on input ⟨w⟩:
1: Run M on x
2: if M accepts x then, run R on input w and output the
3: else reject
• (⟨M⟩,x) ∈ LACC =⇒ M accepts x =⇒ L(M′) = L(R) ∈ P =⇒ T(⟨M′⟩) accepts =⇒ D accepts (⟨M⟩,x).
• (⟨M⟩,x) ̸∈ LACC =⇒ M does not accept x =⇒ L(M′) = ∅ ̸∈ P =⇒ T(⟨M′⟩) rejects =⇒ D rejects (⟨M⟩,x).
We have shown LACC ≤T LP. Since LACC is undecidable, we conclude that LP is undecidable. The case of P being trivial is exactly analogous to the above case, where A is unrecognizable, and so LA = ∅ is decidable. We now prove the analog for A being recognizable. Our proof that LP is undecidable is going to be almost exactly the same as the proof LA being undecidable – in
fact we will construct the exact same decider in our Turing Reduction.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 7 6 Review Topics
The midterm covers two units: algorithms and computability. Anything material covered in lecture, homework, or discussion is fair game for the exam. As a guideline, you should be comfortable with the following topics.
6.1 Algorithms
1. Potential function analysis: Euclidean Algorithm 2. Divide and conquer
(a) examples: mergesort, Karatsuba integer multiplication
(b) analysis techniques: Master’s Theorem, non-Master’s-Theorem recurrences
3. Dynamic programming
(a) examples: LCS, 0-1 Knapsack, Floyd-Warshall
(b) algorithmic techniques: recurrences, “top-down” and “bottom-up” approaches
4. Greedy algorithms
(a) examples: Kruskal, change dispenser
(b) techniques: proving and disproving optimality
6.2 Computability
1. Languages
(a) definitions: language as subset of Σ⋆, accepting/rejecting
(b) undecidable languagues: LHALT, LACC, L∅, LEQ, LACC, LHALT 2. Deterministic Finite Automata (DFA)
(a) 5-tuple definition (b) designing DFA
(c) identify language DFA decides 3. Turing Machines
(a) 7-tuple definition
(b) equivalence of TM variations (two tapes)
(c) Differen
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com