Decidability and Computability

Math for CS · Axiom Academy

Decidability and Computability The limits of what any algorithm can ever compute Step 1: Three Buckets of Languages Every language over an alphabet falls into exactly one of three classes — and most fall into the worst one. Decidable (a.k.a. recursive): some Turing machine M halts on every input and accepts exactly the strings in L . You always get a definitive yes/no answer. Recognizable (a.k.a. recursively enumerable, RE): some TM accepts exactly the strings in L , but it might loop forever on inputs not in L . Unrecognizable : no TM at all recognizes L . Both inclusions are strict. The strictness on the right is a counting argument: there are uncountably many languages but only countably many Turing machines, so most languages are not even recognizable. Decidable problems are the friendly ones. Here are several from automata theory. . Decidable: simulate B on w for |w| steps and report the result. . Decidable: mark all states reachable from the start. Accept iff no marked state is final. . Decidable: build the symmetric-difference DFA C and decide on C . . Decidable: convert to Chomsky normal form and try all derivations of length . Every "yes/no" question about finite machines (DFAs, NFAs, CFGs) tends to be decidable, because we can analyze the machine's structure directly. The trouble starts when the machine being analyzed is itself a Turing machine — then we lose the ability to predict whether it will halt.

This is the written version of the interactive lesson above. See the full Math for CS course.