What computability is about
Most programming questions are about how to do something well: faster, shorter, clearer. Computability theory asks a more basic question: can it be done by a program at all, given unlimited time and space? Nothing about speed or elegance comes into it. A task is either something an algorithm can carry out, or it is not.
The field grew in the 1930s, before electronic computers existed, out of questions in mathematical logic. People wanted to know what it means for a procedure to be “effective,” meaning something that could be carried out mechanically by following rules without insight. Several researchers gave precise definitions, and those definitions turned out to describe the same set of tasks. That surprising agreement is the foundation everything else rests on.
For a reader interested in esoteric programming languages, the theory is useful because it explains why a language with a handful of instructions can still be fully powerful, and why some questions about even a tiny program have no general answer.
Problems, functions and decisions
Computability theory usually works with decision problems: questions with a yes or no answer for every input. “Is this number prime?” is one. “Does this text contain the word cat?” is another. Any task can be dressed up as a decision problem, which keeps the theory tidy.
A problem is called decidable if some algorithm always finishes and gives the correct yes or no answer for every possible input. Primality is decidable, since trial division always terminates. A problem is undecidable if no such algorithm can exist, not merely because nobody has found one yet, but because it can be proved that none can be written.
There is a middle category, sometimes called semi-decidable. For these problems an algorithm can confirm every yes answer eventually, but it may run forever on a no answer. Searching for a proof or running a program to see whether it stops are typical examples.
Models of computation
To prove something cannot be computed, you first need a precise definition of computing. The common models include:
- The Turing machine, with a tape, a head and a table of rules.
- The lambda calculus, built entirely from function definition and application.
- Recursive functions, built from arithmetic and a few combining rules.
- Rewriting systems, where text is transformed by rules.
The remarkable fact is that these all compute exactly the same functions. The Church-Turing thesis is the claim that this shared set matches what we informally mean by “computable.” Notably it is a claim and not a proved theorem, because “informal notion” cannot be part of a proof.
Weaker models exist too. Finite automata have fixed memory and recognize only simple patterns. Pushdown machines add a stack and gain some power, but still fall short of a full Turing machine. Placing a system on this ladder tells you what it can express.
Universality and Turing completeness
A system is universal, or Turing complete, if it can simulate any Turing machine. Turing completeness is the working test people use for programming languages. The usual way to show it is to write a simulation or translation of something already known to be universal, which is also how a completeness proof for an unusual language typically proceeds.
What stands out is how little is needed. A tape with a few operations, a pair of counters with increment and conditional decrement (the basis of counter machines), a simple cellular automaton, or a small set of rewriting rules can each be enough. Rule 110 and the Game of Life are well-known examples of simple systems that can, in principle, perform any computation.
Limits that no cleverness removes
The best-known limit is the halting problem: there is no program that, given any program and input, always correctly says whether it eventually stops. The proof uses a self-referential trick rather than any engineering limitation, so a faster computer or a smarter programmer cannot get around it.
Many other questions inherit this difficulty. A broad result known as Rice’s theorem says that any nontrivial question about what a program does, as opposed to how its text looks, is undecidable in general. Asking whether a program ever prints a certain character, whether a given piece of dead code is ever reached, or whether two programs behave identically all fall into this family. Specific programs can often be analyzed anyway; the limit is on a single method that works for all of them.
Theory versus real machines
Models assume unbounded memory, and real computers have a fixed amount. Strictly speaking, a physical machine has a finite number of states, so in principle every question about it is decidable, although the state count is so large that the answer is useless in practice. Theory therefore treats real machines as approximations of idealized ones, and that is a convention worth understanding rather than a flaw. The difference shows up in debates over whether a language such as Befunge counts as Turing complete when its playfield is limited.
It also helps to keep computability separate from complexity. Computability asks whether a solution exists at all. Complexity asks how much time or space it needs. A problem can be perfectly decidable and still be hopelessly slow.
How to use these ideas
When you meet a new esoteric language, a few questions bring structure to it. What is its memory model? Can it loop without bound? Can it make decisions based on data? If the answers are yes, and memory is effectively unlimited, the language is probably universal, and you can try to prove it by writing an interpreter or translation for a known universal system. If memory is fixed and small, the language is more likely equivalent to a finite automaton, no matter how strange its syntax.
The other articles in this section take each of these threads further: the machines themselves, the halting argument, the thesis behind it all, and how the ideas apply to grid-based languages.