Decidability in Theory of Computation

Decidability

• A language, L, is considered decidable if a Turing machine, M, exists.
• M must halt on every input.
• If a string w is a member of L, M accepts w.
• If a string w is not a member of L, M rejects w.
• In essence, a decider (a Turing machine that always halts) can determine language membership for any input.

Examples of Decidable Languages

A_DFA

• A_DFA = {<B, w> | B is a DFA that accepts w}
• Proof is achieved by simulating DFA B on input w: accept if the simulation ends in an accepting state; reject if it ends in a non-accepting state.
• A DFA always halts after reading the entire input string.

A_CFG

• A_CFG = {<G, w> | G is a CFG that generates w}
• Involves converting G to Chomsky Normal Form (CNF).
• If w = ε and G generates ε, accept; if w = ε and G does not generate ε, reject.
• If w ≠ ε, list all derivations of length |w| and check if any yield w; accept if found, reject otherwise.
• The Turing machine halts because there is a finite number of derivations to check.

Emptiness Testing for CFGs

• E_CFG = {<G> | G is a CFG such that L(G) = ∅}
• Algorithms involve marking all terminal symbols in G.
• One then repeats until no new variables get marked by marking any variable A if G has a rule A -> Y1 Y2 ... Yk where each symbol Y1, Y2, ..., Yk has already been marked.
• Accept if the start variable is not marked; reject, otherwise.
• The algorithm always terminates, determining if the CFG can generate any terminal string.

Undecidable Languages

Introduction

• Not all languages are decidable.

A_TM

• A_TM = {<M, w> | M is a TM that accepts w}
• A fundamental example of an undecidable language.

Implications

• The existence of undecidable languages puts limits on computation, meaning there are problems for which no algorithm can solve them in all cases.

Proof Strategies

Proving "If P, then Q"

• Trivial Proof: If Q is true.
• Vacuous Proof: If P is false.
• Direct Proof: Assume P is true, show that Q is true based of this assumption.
• Contrapositive Proof: Assume Q is false and show that P is false.
• Proof by Contradiction: Assume P is true and Q is false, and show that a contradiction results.

Proof by Cases

• To prove P, establish P1 ∨ P2 ∨ ... ∨ Pn, and then show that P1 → Q, P2 → Q,..., Pn → Q.

Proof by Counterexample

• To show that ∀x P(x) is false, it is enough to find one x where P(x) is false.

Existence Proofs

Constructive Existence Proof

• Find an explicit value of c for which P(c) is true

Nonconstructive Existence Proof

• Demonstrates existence of c without an actual finding it

Inference of Rules

Modus Ponens (MP)

• Given P → Q and P, conclude Q.

Modus Tollens (MT)

• Given P → Q and ¬Q, one can conclude ¬P.

Hypothetical Syllogism (HS)

• Given P → Q and Q → R, conclude P → R.

Disjunctive Syllogism (DS)

• Given P ∨ Q and ¬P, or P ∨ Q and ¬Q, conclude Q or P, respectively.

Simplification (Simp)

• Given P ∧ Q, conclude P (or Q).

Adjunction (Adj)

• Given P and Q, conclude P ∧ Q.

Addition (Ad)

• Given P, you can conclude P ∨ Q for any Q.

Double Negation (DN)

• P is logically equivalent to ¬¬P.