IMG_3084.jpeg

# Lecture 18: Decidability ## Goals - Review the Church-Turing thesis. - Decide properties of regular and context-free languages. - Introduce the Halting Problem. ## The Church-Turing Thesis ### Intuition "Any well-defined computation can be performed by a Turing machine." ### Impact - Since...

# Lecture 18: Decidability ## Goals - Review the Church-Turing thesis. - Decide properties of regular and context-free languages. - Introduce the Halting Problem. ## The Church-Turing Thesis ### Intuition "Any well-defined computation can be performed by a Turing machine." ### Impact - Since the 1930s, every model of computation proposed has been shown to be equivalent to a Turing machine. - A problem is algorithmically *decidable* if it can be expressed as a Turing machine (an algorithm) that always halts with the correct answer. - A problem is algorithmically *undecidable* if no such Turing machine exists. ## Decidability ### Acceptance Problem for DFAs $A_{DFA} = \{\langle B, w \rangle \mid B \text{ is a DFA that accepts input } w \}$ ### Theorem $A_{DFA}$ is a decidable language. ### Proof - Simulate $B$ on input $w$. - If $B$ accepts $w$, accept. If $B$ rejects $w$, reject. ## Decidability (cont.) ### Acceptance Problem for NFAs $A_{NFA} = \{\langle B, w \rangle \mid B \text{ is an NFA that accepts input } w \}$ ### Theorem $A_{NFA}$ is a decidable language. ### Proof - Convert $B$ to an equivalent DFA $C$. - Simulate $C$ on input $w$. - If $C$ accepts $w$, accept. If $C$ rejects $w$, reject. ## Decidability (cont.) ### Acceptance Problem for Regular Expressions $A_{REX} = \{\langle R, w \rangle \mid R \text{ is a regular expression that generates } w \}$ ### Theorem $A_{REX}$ is a decidable language. ### Proof - Convert $R$ to an equivalent DFA $B$. - Simulate $B$ on input $w$. - If $B$ accepts $w$, accept. If $B$ rejects $w$, reject. ## Decidability (cont.) ### Emptiness Testing for DFAs $E_{DFA} = \{\langle A \rangle \mid A \text{ is a DFA and } L(A) = \emptyset\}$ ### Theorem $E_{DFA}$ is a decidable language. ### Proof - Determine if there is a path from the start state to an accept state in $A$. - If yes, reject. If no, accept. ## Decidability (cont.) ### Equivalence Testing for DFAs $EQ_{DFA} = \{\langle A, B \rangle \mid A \text{ and } B \text{ are DFAs and } L(A) = L(B) \}$ ### Theorem $EQ_{DFA}$ is a decidable language. ### Proof - Construct DFA $C = (A \cap \overline{B}) \cup (\overline{A} \cap B)$. - Test whether $L(C) = \emptyset$. - If yes, accept. - If no, reject. ## Decidability of CFLs ### Acceptance Problem for CFGs $A_{CFG} = \{\langle G, w \rangle \mid G \text{ is a CFG that generates } w \}$ ### Theorem $A_{CFG}$ is a decidable language. ### Proof - Convert $G$ to Chomsky normal form. - Enumerate all derivations of length $2|w| - 1$. - If any derivation generates $w$, accept. - If all derivations do not generate $w$, reject. ## Decidability of CFLs (cont.) ### Emptiness Testing for CFGs $E_{CFG} = \{\langle G \rangle \mid G \text{ is a CFG and } L(G) = \emptyset\}$ ### Theorem $E_{CFG}$ is a decidable language. ### Proof - For each terminal $t$, mark $t$ if the production $t \rightarrow t$. - Repeat until no new variables are marked: - Mark any variable $A$ if $G$ contains a production $A \rightarrow U_1 U_2 \dots U_k$ and each symbol $U_1 \dots U_k$ has already been marked. - If the start variable is not marked, accept. Otherwise, reject. ## Undecidability ### The Halting Problem $A_{TM} = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ accepts input } w \}$ ### Theorem $A_{TM}$ is undecidable. ### Proof - Assume that a TM $H$ decides $A_{TM}$. - Construct a TM $D$ that calls $H$ as a subroutine, then reverses the answer. ``` D(M): Run H(M, ) If H accepts, reject. If H rejects, accept. ``` - Run $D(D)$: - If $H$ accepts, $D$ rejects, contradiction. - If $H$ rejects, $D$ accepts, contradiction. - Therefore, $H$ must not exist. ## Computation History ### Definition Let $M$ be a Turing machine and $w$ an input string. - An accepting computation history for $M$ on $w$ is a sequence of configurations $C_0, C_1, \dots, C_l$, where $C_0$ is the start configuration of $M$ on $w$, each $C_i$ legally follows from $C_{i-1}$ according to $M$'s transition function, and $C_l$ is an accepting configuration. - A rejecting computation history for $M$ on $w$ is defined similarly, except that $C_l$ is a rejecting configuration. ### Properties - $M$ accepts $w$ iff there exists an accepting computation history. - $M$ rejects $w$ iff there exists a rejecting computation history. - $M$ loops on $w$ iff there exists neither. - Computation histories are finite.