Computability theory (also called recursion theory) is the branch of theoretical computer science that studies what problems can be solved by algorithms and what problems cannot. It addresses fundamental questions about the limits of computation: Which problems are solvable? Which are unsolvable? What are the boundaries between what computers can and cannot do? The field was founded by Alan Turing and Alonzo Church in the 1930s, who independently developed equivalent models of computation and discovered that there are fundamental limits to what can be computed. The most famous result is the undecidability of the halting problem—the impossibility of creating a program that can determine whether any other program will halt or run forever. This article explores computability theory, the Church-Turing thesis, decidability, the halting problem, and the implications for computer science.

In Simple Terms

Computability theory asks: "What can computers do, and what can't they do?" It turns out that there are some problems that are fundamentally impossible for any computer to solve, no matter how powerful. The most famous example is the halting problem: can we write a program that looks at any other program and tells us whether it will finish running or get stuck in an infinite loop? The answer is no—this is impossible, not because we're not smart enough, but because it's mathematically impossible. Computability theory helps us understand these fundamental limits. It tells us which problems we can hope to solve with computers and which ones we should give up on. It's like knowing the rules of the game before you start playing—some things are just not possible, and it's important to know what those things are.

Introduction

Computability theory addresses one of the most fundamental questions in computer science: What can be computed? This question was first rigorously addressed in the 1930s by Alan Turing and Alonzo Church, who independently developed mathematical models of computation and discovered that there are problems that cannot be solved by any algorithm, no matter how powerful the computer.

The field emerged from attempts to formalize the intuitive notion of "algorithm" or "effective procedure." Mathematicians wanted to know: What does it mean for a problem to be solvable? Are there problems that are inherently unsolvable? The answers revolutionized our understanding of computation and established fundamental limits that apply to all computers, past, present, and future.

The Church-Turing Thesis

The Church-Turing thesis is the foundational principle of computability theory:

Any function that can be computed by an algorithm can be computed by a Turing machine.

This thesis, while not provable (it's a statement about physical reality and intuitive notions of computation), is widely accepted and forms the foundation of theoretical computer science. It implies:

• Every program that can be written in any programming language can be simulated by a Turing machine
• If a problem cannot be solved by a Turing machine, it cannot be solved by any computer
• Turing machines define the fundamental limits of computation

Historical Context: The thesis is named after Alonzo Church (who used lambda calculus) and Alan Turing (who used Turing machines), who independently arrived at equivalent models of computation in 1936. Their work showed that these very different mathematical models capture the same notion of computability.

Evidence for the Thesis:

• All known models of computation (Turing machines, lambda calculus, recursive functions, etc.) have been shown to be equivalent
• No physically realizable model of computation has been found that can compute more than Turing machines
• The thesis has withstood decades of scrutiny and is universally accepted in computer science

Decidability

A problem is decidable (or computable) if there exists a Turing machine that:

• Halts on all inputs
• Correctly solves the problem for all inputs

A problem is undecidable (or uncomputable) if no Turing machine can solve it for all inputs.

Examples of Decidable Problems:

• Determining if a number is prime
• Sorting a list of numbers
• Finding the shortest path in a graph
• Checking if a string matches a regular expression
• Determining if a program has a syntax error

Examples of Undecidable Problems:

• The halting problem
• Determining if two programs are equivalent
• Determining if a program will ever print a specific output
• Most non-trivial properties of programs (Rice's theorem)

The Halting Problem

The halting problem is the most famous undecidable problem:

Given a Turing machine (or program) and an input, determine whether the machine will eventually halt or run forever.

Turing's Proof (1936): Turing proved that the halting problem is undecidable using a diagonalization argument. The proof proceeds by contradiction:

1. Assume there exists a Turing machine H that solves the halting problem
2. Construct a machine D that uses H to create a contradiction
3. Show that D cannot exist, therefore H cannot exist

Sketch of the Proof:

• Suppose H(M, x) returns "halts" if machine M halts on input x, and "runs forever" otherwise
• Construct machine D that, on input M, runs H(M, M) and does the opposite
• If H(M, M) says "halts", D runs forever; if H(M, M) says "runs forever", D halts
• What happens when we run D on itself (D(D))?
  • If H(D, D) says "halts", then D(D) runs forever—contradiction!
  • If H(D, D) says "runs forever", then D(D) halts—contradiction!
• Therefore, H cannot exist

Implications:

• Not all problems are solvable
• There are fundamental limits to what computers can do
• Some questions about computation are inherently unanswerable
• This applies to all models of computation (not just Turing machines)
• We cannot write a program that can analyze arbitrary programs and determine their behavior

Other Undecidable Problems

Many problems are undecidable, including:

Post Correspondence Problem

Given two sets of strings (dominoes), can they be arranged to form matching sequences? This problem is undecidable and is often used to prove other problems undecidable.

Rice's Theorem

Rice's theorem states that any non-trivial property of programs is undecidable. A property is "non-trivial" if:

• Some programs have the property
• Some programs don't have the property

Examples of Undecidable Properties (by Rice's theorem):

• Does a program always halt?
• Does a program compute a specific function?
• Will a program ever print "hello world"?
• Are two programs equivalent?

Trivial Properties (decidable):

• Does a program have at least one line of code? (all programs do)
• Does a program have zero lines of code? (no program does)

Busy Beaver Problem

What is the maximum number of steps a halting Turing machine with n states can take? This problem grows faster than any computable function and is undecidable.

Tiling Problem

Given a set of tiles, can they tile the infinite plane? This problem is undecidable and has connections to logic and computation.

Recursive and Recursively Enumerable Languages

A language is recursively enumerable (or semi-decidable) if there exists a Turing machine that:

• Accepts all strings in the language
• May not halt on strings not in the language

A language is recursive (or decidable) if there exists a Turing machine that:

• Accepts all strings in the language
• Rejects all strings not in the language
• Always halts

Key Distinction: Recursive languages are a subset of recursively enumerable languages. Every recursive language is recursively enumerable, but not every recursively enumerable language is recursive.

Examples:

• The set of all valid programs in a programming language is recursive (can be checked by a parser)
• The set of all halting programs is recursively enumerable but not recursive (halting problem)
• The set of all non-halting programs is not even recursively enumerable

Reducibility

Reducibility is a key technique for proving problems undecidable:

Problem A reduces to Problem B if solving Problem B would allow us to solve Problem A.

If Problem A is undecidable and Problem A reduces to Problem B, then Problem B is also undecidable.

Example: Many problems are proven undecidable by reducing the halting problem to them:

• Program equivalence reduces to halting problem
• Program termination reduces to halting problem
• Many verification problems reduce to halting problem

Implications for Computer Science

Computability theory has profound implications:

Limits of Computation

• Not all problems are solvable
• There are fundamental limits that apply to all computers
• Some questions are inherently unanswerable

Program Analysis

• We cannot write a perfect program analyzer
• Static analysis tools have limitations
• Some program properties cannot be automatically verified

Verification and Testing

• We cannot automatically verify all program properties
• Some bugs are undecidable to detect
• Testing and verification must focus on decidable properties

Algorithm Design

• Understanding decidability helps identify which problems are solvable
• Reducibility helps classify problem difficulty
• Some problem variations are decidable while others are not

Relationship to Other Topics

Computability theory is foundational for:

• Turing Machines: The model of computation used in computability theory
• Complexity Theory: Studies efficiently solvable problems (assumes problems are decidable)
• Formal Languages: Classifies languages by their decidability properties
• Computer Science: Provides the theoretical foundation
• Discrete Mathematics: Uses logic and set theory