Computability Theory

Overview

Computability theory studies the fundamental limits of computation: which problems can be solved by algorithms and which are inherently uncomputable. These results reveal deep connections between mathematics and computation.

1. Church-Turing Thesis

1.1 Core Claim

Church-Turing thesis: Any function that can be "effectively computed" can be computed by a Turing machine.

This is not a theorem (it cannot be proved) but rather a definition/hypothesis that equates the intuitive notion of "computable" with the mathematical definition provided by Turing machines.

1.2 Equivalent Computational Models

Multiple independently developed computational models have been proved equivalent:

Model	Originator	Year
Turing machine	Turing	1936
$\lambda$-calculus	Church	1936
$\mu$-recursive functions	Kleene	1936
Post systems	Post	1936
Markov algorithms	Markov	1951

The equivalence of these models provides strong evidence for the Church-Turing thesis.

2. Decidability and Recognizability

2.1 Basic Definitions

Turing-recognizable (recursively enumerable, RE): There exists a Turing machine $M$ such that

\[ L(M) = \{w \mid M \text{ accepts on input } w\} \]

$M$ may never halt on inputs not in $L$.

Turing-decidable (recursive, decidable): There exists a Turing machine $M$ such that for every input $w$:

$w \in L \implies M$ accepts
$w \notin L \implies M$ rejects

$M$ halts on all inputs.

2.2 Hierarchy of Language Classes

graph TB
    DEC["Decidable Languages<br>(Decidable)"]
    RE["Turing-Recognizable<br>(RE)"]
    coRE["co-RE"]
    ALL["All Languages"]
    DEC --> RE --> ALL
    DEC --> coRE --> ALL

Key theorem: $L$ is decidable $\iff$ both $L$ and $\overline{L}$ are Turing-recognizable.

3. The Halting Problem

3.1 Problem Definition

Halting problem $HALT$:

\[ HALT = \{\langle M, w \rangle \mid M \text{ is a Turing machine and } M \text{ halts on input } w\} \]

3.2 Undecidability Proof (Diagonalization)

Theorem: $HALT$ is undecidable.

Proof (by contradiction):

Assume there exists a decider $H$ such that:

\[ H(\langle M, w \rangle) = \begin{cases} \text{accept} & \text{if } M \text{ halts on } w \\ \text{reject} & \text{if } M \text{ does not halt on } w \end{cases} \]

Construct a Turing machine $D$:

\[ D(\langle M \rangle) = \begin{cases} \text{reject} & \text{if } H(\langle M, \langle M \rangle \rangle) = \text{accept} \\ \text{loop forever} & \text{if } H(\langle M, \langle M \rangle \rangle) = \text{reject} \end{cases} \]

Consider $D(\langle D \rangle)$:

If $D$ halts on $\langle D \rangle$ $\implies$ $H$ accepts $\implies$ $D$ rejects (halts)... loop
If $D$ does not halt on $\langle D \rangle$ $\implies$ $H$ rejects $\implies$ $D$ loops forever...

Either case leads to a contradiction. Therefore $H$ does not exist. $\square$

The Idea of Diagonalization

This proof method is essentially the same as Cantor's diagonalization argument proving the uncountability of the reals. The behavior of $D$ contradicts the hypothesized $H$ "on the diagonal."

3.3 Significance of the Halting Problem

$HALT$ is Turing-recognizable (just simulate the execution), but not decidable
$\overline{HALT}$ is not Turing-recognizable
A fundamental limitation on program verification: no universal program termination checker exists

4. Examples of Decidable Problems

4.1 Decidable Problems About DFAs

Problem	Description	Decidability
$A_{DFA}$	Does the DFA accept string $w$?	Decidable, $O(
$E_{DFA}$	Is the language of the DFA empty?	Decidable, $O(
$EQ_{DFA}$	Are two DFAs equivalent?	Decidable

4.2 Decidable Problems About CFGs

Problem	Description	Decidability
$A_{CFG}$	Does the CFG generate string $w$?	Decidable (CYK, $O(n^3)$)
$E_{CFG}$	Is the language of the CFG empty?	Decidable
$EQ_{CFG}$	Are two CFGs equivalent?	Undecidable

4.3 Undecidable Problems About Turing Machines

Problem	Description
$A_{TM}$	Does the Turing machine accept string $w$?
$HALT_{TM}$	Does the Turing machine halt on the input?
$E_{TM}$	Is the language of the Turing machine empty?
$EQ_{TM}$	Are two Turing machines equivalent?

5. Reductions

5.1 Mapping Reductions

Definition: Language $A$ mapping reduces to $B$ (written $A \leq_m B$) if there exists a computable function $f: \Sigma^* \to \Sigma^*$ such that:

\[ w \in A \iff f(w) \in B \]

Meaning of reduction: $B$ is at least as hard as $A$.

Theorems:

If $A \leq_m B$ and $B$ is decidable, then $A$ is decidable
If $A \leq_m B$ and $A$ is undecidable, then $B$ is undecidable

5.2 Reduction Example

Proving $E_{TM}$ is undecidable:

Reduce $A_{TM}$ to $\overline{E_{TM}}$.

Given $\langle M, w \rangle$, construct Turing machine $M'$:

\[ M'(x) = \begin{cases} \text{accept} & \text{if } x = w \text{ and } M \text{ accepts } w \\ \text{reject} & \text{otherwise} \end{cases} \]

Then:

$M$ accepts $w \iff L(M') = \{w\} \neq \emptyset \iff \langle M' \rangle \in \overline{E_{TM}}$
$M$ does not accept $w \iff L(M') = \emptyset \iff \langle M' \rangle \in E_{TM}$

Therefore $A_{TM} \leq_m \overline{E_{TM}}$. Since $A_{TM}$ is undecidable, $\overline{E_{TM}}$ is also undecidable, and hence $E_{TM}$ is undecidable as well. $\square$

6. Rice's Theorem

6.1 Statement

Rice's theorem: Any nontrivial property of the language recognized by a Turing machine is undecidable.

Formally: Let $P$ be a property of Turing-recognizable languages (i.e., a subset of the set of RE languages). If $P$ is nontrivial ($P \neq \emptyset$ and $P \neq$ all RE languages), then:

\[ L_P = \{\langle M \rangle \mid L(M) \in P\} \]

is undecidable.

6.2 Applications

The following problems are all undecidable (because they are all nontrivial properties of the language recognized by a Turing machine):

Does a Turing machine recognize the empty language?
Does a Turing machine recognize a regular language?
Does a Turing machine recognize a finite language?
Does a Turing machine recognize $\Sigma^*$?

Limitations of Rice's Theorem

Rice's theorem applies only to properties of the language (input-output behavior), not to structural properties of the Turing machine itself. For example, "does the Turing machine have 100 states" is decidable (directly inspect the encoding).

7. Recursion Theorem

7.1 Statement

Recursion theorem (Kleene's fixed-point theorem): For any computable function $t: \Sigma^* \times \Sigma^* \to \Sigma^*$, there exists a Turing machine $R$ such that for all inputs $w$:

\[ R(w) = t(\langle R \rangle, w) \]

That is, a Turing machine can obtain its own description.

7.2 Intuitive Understanding

The recursion theorem states that self-reference is computable:

Programs can print their own source code (Quines)
It provides a tool for an alternative proof of the halting problem
Theoretical foundation for the self-replication mechanism of computer viruses

7.3 Application: Alternative Proof of the Halting Problem

Assume $H$ decides $HALT$. Construct Turing machine $B$:

$B$ on input $w$:

Obtain its own description $\langle B \rangle$ via the recursion theorem
Run $H(\langle B, w \rangle)$
If $H$ says halt, then loop; if $H$ says does not halt, then halt

No matter what $H$ answers, $B$'s actual behavior is always the opposite of $H$'s prediction. Contradiction. $\square$

8. Overview of Undecidable Problems

graph TD
    HALT[Halting Problem] --> ATM[Acceptance Problem A_TM]
    ATM --> ETM[Emptiness Problem E_TM]
    ATM --> EQTM[Equivalence Problem EQ_TM]
    HALT --> PCP[Post Correspondence Problem]
    PCP --> EQCFG[CFG Equivalence]
    HALT --> RICE[All Problems Covered by Rice's Theorem]
    HALT --> HILBERT[Hilbert's Tenth Problem]

Classic undecidable problems:

Problem	Description
Halting problem	Does a program terminate?
Post Correspondence Problem (PCP)	A string matching problem
Hilbert's tenth problem	Does a Diophantine equation have a solution?
Word problem (group theory)	Are two words equal in a group?
Wang tiling problem	Can a set of tiles tile the plane?

References

Sipser, Introduction to the Theory of Computation, Chapters 3-6
Hopcroft, Motwani & Ullman, Introduction to Automata Theory

Related sections:

Problem	Description	Decidability
\(A_{DFA}\)	Does the DFA accept string \(w\)?	Decidable, $O(
\(E_{DFA}\)	Is the language of the DFA empty?	Decidable, $O(
\(EQ_{DFA}\)	Are two DFAs equivalent?	Decidable

Problem	Description	Decidability
\(A_{CFG}\)	Does the CFG generate string \(w\)?	Decidable (CYK, \(O(n^3)\))
\(E_{CFG}\)	Is the language of the CFG empty?	Decidable
\(EQ_{CFG}\)	Are two CFGs equivalent?	Undecidable

Problem	Description
\(A_{TM}\)	Does the Turing machine accept string \(w\)?
\(HALT_{TM}\)	Does the Turing machine halt on the input?
\(E_{TM}\)	Is the language of the Turing machine empty?
\(EQ_{TM}\)	Are two Turing machines equivalent?