What is the difference between primitive recursive and general recursive functions?

Primitive recursive functions are built using bounded loops and always terminate, but they do not capture every computable function. Adding unbounded minimization, a search that may run indefinitely, yields the general recursive functions, which coincide exactly with the Turing-computable functions.

How can a machine with just two counters be as powerful as a computer?

Minsky showed that two registers holding natural numbers, with only increment, decrement, and test-for-zero, can simulate a Turing machine by encoding its tape into the registers. The construction is highly inefficient, but it proves that minimal hardware already reaches the full power of computation.

Recursive Functions and Register Machines

Recursive function theory builds the computable functions from a handful of basic operations, while register machines compute with whole numbers stored in registers, two models that bracket the Turing machine and confirm the robustness of computability.

Definition

The general recursive functions are those built from constants, successor, and projections by composition, primitive recursion, and unbounded minimization; register machines are abstract devices that compute by incrementing, decrementing, and testing the contents of a finite set of registers holding natural numbers.

Scope

This topic covers the primitive recursive functions, the addition of unbounded minimization to obtain the general recursive functions, the Ackermann function as a computable function that is not primitive recursive, register and counter machines and their universality, and the equivalence of all these models with Turing computability.

Core questions

How can the computable functions be defined arithmetically without any machine?
Why is unbounded minimization needed beyond primitive recursion?
How do simple register machines achieve the full power of computation?
Why do these arithmetic and machine models coincide with Turing machines?

Key theories

Equivalence with Turing computability: The general recursive functions and the functions computed by register machines are exactly the Turing-computable functions, reinforcing the Church–Turing thesis through models defined in purely arithmetic and elementary machine terms.
Beyond primitive recursion: The Ackermann function is total and computable yet grows too fast to be primitive recursive, showing that unbounded search is essential and that the primitive recursive functions are a proper subclass of the computable ones.
Universality of register machines: Minsky showed that a machine with only two counters and the operations of increment, decrement, and zero-test is already Turing-complete, an extreme demonstration of how little structure full computation requires.

Clinical relevance

Register machines model the integer arithmetic of real processors more directly than tapes do, primitive recursion corresponds to programs that always terminate and underlies total functional languages and termination analysis, and the recursive-function view connects computation to the foundations of mathematics.

History

Gödel and Herbrand defined the general recursive functions in the early 1930s, and Kleene developed the theory, including the role of minimization. Ackermann had earlier exhibited his fast-growing function, and Minsky introduced register and counter machines in the 1960s, proving even two-counter machines universal.

Key figures

Kurt Gödel
Stephen Kleene
Wilhelm Ackermann
Marvin Minsky

Seminal works

cutland1980
minsky1967

Frequently asked questions

What is the difference between primitive recursive and general recursive functions?: Primitive recursive functions are built using bounded loops and always terminate, but they do not capture every computable function. Adding unbounded minimization, a search that may run indefinitely, yields the general recursive functions, which coincide exactly with the Turing-computable functions.
How can a machine with just two counters be as powerful as a computer?: Minsky showed that two registers holding natural numbers, with only increment, decrement, and test-for-zero, can simulate a Turing machine by encoding its tape into the registers. The construction is highly inefficient, but it proves that minimal hardware already reaches the full power of computation.