ToC_chapter_4_slides
View on GitHub | Download Local
Extracted Content (for search)
Click to view slide text
Theory of Computation Decidability Dimitris Diochnos School of Computer Science University of Oklahoma
D. Diochnos (OU - CS)
Theory of Computation: Decidability
1 / 28
Outline
1
Introduction
2
Decidable Languages
3
Brief Recap of Set-Theoretic notions
4
The Acceptance Problem
D. Diochnos (OU - CS)
Theory of Computation: Decidability
2 / 28
Introduction
Table of Contents
1
Introduction
2
Decidable Languages
3
Brief Recap of Set-Theoretic notions
4
The Acceptance Problem
D. Diochnos (OU - CS)
Theory of Computation: Decidability
3 / 28
Introduction
Introduction
Objective Explore the limits of algorithmic solvability
Why study solvability? Useful to know when a problem is unsolvable ⇒ Need to modify the problem if we need some algorithmic solution Cultural ⇒ Gain better perspective on computation, what computers can and cannot do
D. Diochnos (OU - CS)
Theory of Computation: Decidability
4 / 28
Decidable Languages
Table of Contents
1
Introduction
2
Decidable Languages
3
Brief Recap of Set-Theoretic notions
4
The Acceptance Problem
D. Diochnos (OU - CS)
Theory of Computation: Decidability
5 / 28
Decidable Languages
Decidable Problems Concerning Regular Languages
ADFA = {⟨B, w⟩ | B is a DFA that accepts input string w} The language ADFA expresses the acceptance problem for DFAs. This language contains all the encodings of all DFAs together with strings that the DFAs accept.
D. Diochnos (OU - CS)
Theory of Computation: Decidability
6 / 28
Decidable Languages
Decidable Problems Concerning Regular Languages Theorem 1 The language ADFA = {⟨B, w⟩ | B is a DFA that accepts input string w} is a decidable language. Proof Idea. We need a TM M that decides ADFA . M = “on input ⟨B, w⟩ where B is a DFA and w is a string: 1
Simulate B on input w
2
If the simulation ends in an accept state, accept. If it ends in a non-accepting state, reject.” D. Diochnos (OU - CS)
Theory of Computation: Decidability
7 / 28
Decidable Languages
Decidable Problems Concerning Regular Languages Theorem 2 The language ANFA = {⟨B, w⟩ | B is an NFA that accepts input string w} is a decidable language. Proof Idea. 1 Use the powerset construction and transform the given (assuming valid) NFA N to a DFA C. 2
Then use the TM M from the previous theorem (Theorem 1) and decide the input ⟨C, w⟩.
3
Return the answer that we obtain from M. D. Diochnos (OU - CS)
Theory of Computation: Decidability
8 / 28
Decidable Languages
Decidable Problems Concerning Regular Languages
Theorem 3 The language AREX = {⟨R, w⟩ | R is a regular expression that generates string w} is a decidable language. Proof Idea. 1 Convert R to an NFA A using the conversion that we have seen in class. 2
Now use the TM N from Theorem 2 and return the answer obtained on input ⟨A, w⟩.
D. Diochnos (OU - CS)
Theory of Computation: Decidability
9 / 28
Decidable Languages
Decidable Problems Concerning Regular Languages Theorem 4 The language EDFA = {⟨A⟩ | A is a DFA and L(A) = ∅} is a decidable language. Proof Idea. Create a TM T that propagates marking labels. T = “on input ⟨A⟩ where A is a DFA: 1
Mark the start state of A
2
Repeat until no new states get marked: Mark any state that has a transition coming into it from any state that is already marked
3
If no accept state is marked, accept; otherwise reject.” D. Diochnos (OU - CS)
Theory of Computation: Decidability
10 / 28
Decidable Languages
Decidable Problems Concerning Regular Languages Theorem 5 The language EQDFA = {⟨A, B⟩ | A and B are DFAs and L(A) = L(B)} is a decidable language. Proof Idea. Construct a DFA C that accepts the symmetric difference. L(C) = L(A) △ L(B) = (L(A) ∩ L(B)) ∪ (L(A) ∩ L(B))
D. Diochnos (OU - CS)
Theory of Computation: Decidability
11 / 28
Decidable Languages
Decidable Problems Concerning Context-Free Languages Theorem 6 The language ACFG = {⟨G, w⟩ |G is a CFG that generates string w} is a decidable language. Proof Idea. (It does not work to try all possible derivations, as there is an infinite number of such derivations.) Every CFG in CNF will generate w in 2n − 1 steps, where |w| = n and provided w can be generated by G. ⇒ So finitely many such derivations need to be checked ⇒ If some derivation generates w, accept; otherwise reject. D. Diochnos (OU - CS)
Theory of Computation: Decidability
12 / 28
Decidable Languages
Decidable Problems Concerning Context-Free Languages
Remarks: The above problem is related to compiling programming languages There is a more (much more) efficient way of solving the problem (using dynamic programming; CYK algorithm) Everything we say about CFGs also applies to PDAs
D. Diochnos (OU - CS)
Theory of Computation: Decidability
13 / 28
Decidable Languages
Decidable Problems Concerning Context-Free Languages Theorem 7 ECFG = {⟨G⟩ | G is a CFG and L(G) = ∅} is a decidable language. Proof Idea. For each variable determine if we can generate some string. ⇒ Start from terminals and mark them ⇒ Then mark variables that can yield such terminals ⇒ Then mark variables that can yield the previous variables ⇒ etc In other words, if A → U1 U2 … Uk is a rule of G, mark A when each of U1 U2 … Uk has been marked. So in the end, if the start variable is not marked, accept. otherwise reject. D. Diochnos (OU - CS)
Theory of Computation: Decidability
14 / 28
Decidable Languages
Decidable Problems Concerning Context-Free Languages
What about EQCFQ = {⟨G, H⟩ | G and H are CFGs and L(G) = L(H)}?
Turns out that it is not decidable. CFLs are not closed under complementation or intersection.
D. Diochnos (OU - CS)
Theory of Computation: Decidability
15 / 28
Decidable Languages
Decidable Problems Concerning Context-Free Languages Theorem 8 Every context-free language is decidable. Proof Idea. Use Theorem 6. In other words, let G be a CFG for language A. Then, on input w, use a TM MG that feeds ⟨G, w⟩ into the TM S of Theorem 6. Return whatever S returns. Note that simulating a non-deterministic PDA is a bad idea, because some branches of the computation may go on forever ⇒ We do not have a decider. So, instead, first convert the PDA into a CFG G. D. Diochnos (OU - CS)
Theory of Computation: Decidability
16 / 28
Decidable Languages
Decidable Problems Concerning Context-Free Languages
The relationship among classes of languages D. Diochnos (OU - CS)
Theory of Computation: Decidability
17 / 28
Brief Recap of Set-Theoretic notions
Table of Contents
1
Introduction
2
Decidable Languages
3
Brief Recap of Set-Theoretic notions
4
The Acceptance Problem
D. Diochnos (OU - CS)
Theory of Computation: Decidability
18 / 28
Brief Recap of Set-Theoretic notions
Equal Cardinality Equal cardinality of infinite sets: Create a bijection (correspondence) between the two sets A and B. f is one-to-one: denoted as f : A ↣ B and means that f (a) = f (b) ⇔ a = b f is onto: denoted as f : A → → B and means (∀b ∈ B)(∃a ∈ A)[f (a) = b] f is bijection (correspondence): denoted as f : A ↣ → B and means that every element of A maps to a unique element of B and vice versa For example N = {1, 2, 3… .} and Even = {2, 4, 6, 8, …} have the same cardinality.
D. Diochnos (OU - CS)
Theory of Computation: Decidability
19 / 28
Brief Recap of Set-Theoretic notions
Countable Set Countable Set: Finite set or has same cardinality as N For example |Q| = |N |
D. Diochnos (OU - CS)
Theory of Computation: Decidability
20 / 28
Brief Recap of Set-Theoretic notions
Countable Set Theorem 9 R is uncountable Proof. Idea: Diagonalization f (n) n 1 3.14159 … 2 55.55555 … 3 0.12345 … 4 0.50000 … … . Construct a number that does not appear anywhere in the bijection, by selecting a decimal digit in each position that is different from the respective digit in f (n) (e.g. x = 0.4641 …) ⇒ contradict the existence of f . D. Diochnos (OU - CS)
Theory of Computation: Decidability
21 / 28
The Acceptance Problem
Table of Contents
1
Introduction
2
Decidable Languages
3
Brief Recap of Set-Theoretic notions
4
The Acceptance Problem
D. Diochnos (OU - CS)
Theory of Computation: Decidability
22 / 28
The Acceptance Problem
The Acceptance Problem ATM = {⟨M, w⟩ |M is a TM and M accepts w} Theorem 10 ATM is Turing-recognizable. Proof Idea. U = “On input ⟨M, w⟩ where M is a TM and w is a string: 1
Simulate M on input w
2
If M ever enters its accept state, accept; If M ever enters its reject state, reject.”
U is an example of the universal Turing machine because it is capable of simulating any other Turing machine from the description of that machine. (Such a machine was first used by Turing) D. Diochnos (OU - CS)
Theory of Computation: Decidability
23 / 28
The Acceptance Problem
The Acceptance Problem
Theorem 11 ATM is undecidable. Proof (to be cont.) Towards contradiction, assume ATM is decidable, with the Turing machine H being a decider for ATM . ( accept, if M accepts w H ⟨M, w⟩ = reject, if M does not accept w
D. Diochnos (OU - CS)
Theory of Computation: Decidability
24 / 28
The Acceptance Problem
Proof (cont.) Now look at the following TM: D = “On input ⟨M⟩, where M is a TM: 1
Run H on input ⟨M, ⟨M⟩⟩
2
Output the opposite of what H outputs.”
So,
( accept, D ⟨M⟩ = reject,
if M does not accept ⟨M⟩ if M accepts ⟨M⟩
What about D ⟨D⟩ ? We have ( accept, D ⟨D⟩ = reject,
if D does not accept ⟨D⟩ if D accepts ⟨D⟩
Contradiction either way ⇒ H cannot exist! D. Diochnos (OU - CS)
Theory of Computation: Decidability
25 / 28
The Acceptance Problem
Turing Unrecognizable Languages
A language is co-Turing recognizable if it is the complement of a Turing recognizable language. Theorem 12 A language L is decidable ⇒ L is Turing recognizable and co-Turing recognizable Proof (to be cont.) (⇒) L decidable. Then L and L are both Turing recognizable. (The complement L of a decidable language L is also decidable)
D. Diochnos (OU - CS)
Theory of Computation: Decidability
26 / 28
The Acceptance Problem
Turing Unrecognizable Languages
Proof (cont.) (⇐) Let M1 recognize L and M2 recognize L. Now consider the following TM M. M = “On input w: 1
Run both M1 and M2 on input w in parallel
2
If M1 accepts, accept; if M2 accepts, reject”
For every string w ∈ Σ∗ , we have either w ∈ L or w ∈ L ⇒ Either M1 or M2 accepts w ⇒ M always halts with an answer ⇒ M is a decider for L ⇒ L is decidable.
D. Diochnos (OU - CS)
Theory of Computation: Decidability
27 / 28
The Acceptance Problem
Turing Unrecognizable Languages
Corollary 13 ATM is not Turing-recognizable. Proof. Theorem 12
If ATM was recognizable =⇒ ATM is decidable ⇒ Contradicts the undecidability of ATM (Theorem 11)
D. Diochnos (OU - CS)
Theory of Computation: Decidability
28 / 28