Recursive Function

Function defined in terms of itself; McCarthy’s Lisp made recursion — not iteration — the default mechanism of computation.

In this vault

Recursive Functions of Symbolic Expressions and Their Computation by Machine
Foundations of Logic Programming - Lloyd
General Recursive Functions of Natural Numbers — Kleene 1936, the defining paper for the general-recursive class.
Recursive Predicates and Quantifiers — Kleene 1943, extends the theory to predicates and the arithmetical hierarchy.

Backlinks

On Notation for Ordinal Numbers line 32
On Notation for Ordinal Numbers line 21
An Unsolvable Problem of Elementary Number Theory line 36
An Unsolvable Problem of Elementary Number Theory line 22
On Definable Sets of Positive Integers line 33
On Definable Sets of Positive Integers line 20
Recursive Predicates and Quantifiers line 36
Recursive Predicates and Quantifiers line 22
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I line 25
Recursively Enumerable Sets of Positive Integers and Their Decision Problems line 22
Classes of Recursively Enumerable Sets and Their Decision Problems line 37
Classes of Recursively Enumerable Sets and Their Decision Problems line 24
Recursive Functions of Symbolic Expressions and Their Computation by Machine line 47
General Recursive Functions of Natural Numbers line 36
General Recursive Functions of Natural Numbers line 21

Linked Pages

Recursive Predicates and Quantifiers

Reference: Kleene, Stephen C. (1943). “Recursive predicates and quantifiers.” Transactions of the American Mathematical Society 53(1), 41–73. DOI 10.2307/1990131. Open scan: ams.org / archive.org.

Summary

This paper is the single most influential structural paper of classical recursion theory. Kleene defines what is now called the arithmetical hierarchy: a stratification of sets and predicates on ℕ by the number and alternation of number-quantifiers prefixed to a decidable (recursive) matrix. A predicate is Σ⁰_n if it can be written ∃x₁ ∀x₂ ∃x₃ … R with n alternations and R recursive; Π⁰_n is the dual; Δ⁰_n = Σ⁰_n ∩ Π⁰_n. The recursive sets are precisely Δ⁰_1; the recursively enumerable sets are precisely Σ⁰_1. Each level of the hierarchy is strictly larger than the preceding one — the hierarchy theorem — and Kleene gives universal / complete predicates at each level.

The technical engine is a generalised normal form theorem: any Σ⁰_n predicate can be written with a single bounded block of quantifiers over a primitive recursive matrix, using Kleene’s T-predicate T_n for n-ary partial recursive functions and result-extractor U. The T-predicate first appears here in its mature form. Kleene then proves the enumeration theorem (there is a universal Σ⁰_1 predicate), the s-m-n theorem (recursive parameterisation of indices), and the hierarchy theorem (each level is strictly included in the next), and relates the hierarchy to the jump operator: A' (the halting problem relativised to A) moves one level up.

After 1943 every textbook treatment of computability theory — Rogers, Soare, Odifreddi — is organised around this hierarchy. Rice 1953’s classification of non-trivial index sets is a direct application: the index set of any non-trivial property is at least Σ⁰_1-hard or Π⁰_1-hard, and Rice–Shapiro and later refinements pin them to specific levels.

Key Ideas

Arithmetical hierarchy: Σ⁰_n, Π⁰_n, Δ⁰_n defined by alternation depth of number-quantifiers over a recursive matrix.
Recursive = Δ⁰_1; recursively enumerable = Σ⁰_1: the two “effective” classes located inside the hierarchy.
T-predicate T_n(e, x₁,…,x_n, y): primitive recursive “y codes a computation of {e}(x₁,…,x_n)”; canonical tool of the subject.
Normal form theorem at each level: one bounded matrix of primitive recursive content under n alternating quantifiers.
Enumeration theorem: universal predicate at each Σ⁰_n level.
s-m-n theorem: effective parameterisation of indices.
Hierarchy theorem: strict inclusions Σ⁰_n ⊊ Σ⁰_{n+1}; complete sets exist at each level (e.g. ∅^{(n)}, the nth jump).

Connections

Conceptual Contribution

Claim: The first-order definable subsets of ℕ are organised into a strict hierarchy by quantifier-alternation depth over a recursive matrix; recursive and r.e. sets are its first two levels.
Mechanism: Define Σ⁰_n / Π⁰_n / Δ⁰_n by prefixing n alternating number-quantifiers to recursive matrices; prove normal form via the T-predicate and unbounded search; prove enumeration, s-m-n, and hierarchy theorems by diagonalisation and the jump operator.
Concepts introduced/used: arithmetical hierarchy, T-predicate, s-m-n theorem, enumeration theorem, jump operator, Halting Problem, Recursive Function
Stance: foundational technical paper (recursion theory)
Relates to: Takes the normal form of Kleene 1936 and uses it to build the structural scaffolding that organises all of recursion theory; supplies the classification into which Post 1944 places simple and creative sets and which Rice 1953 uses to classify non-trivial index sets; second-order analogue developed by Mostowski 1946.

General Recursive Functions of Natural Numbers

Reference: Kleene, Stephen C. (1936). “General recursive functions of natural numbers.” Mathematische Annalen 112, 727–766. DOI 10.1007/BF01565439. Open scan: GDZ Göttingen.

Summary

Kleene’s 1936 paper develops the theory of the general recursive functions — the class proposed by Herbrand in correspondence with Gödel and given a precise definition by Gödel in his 1934 Princeton lectures. Kleene formalises the Herbrand–Gödel scheme (systems of equations closed under substitution and replacement of equals) as the official definition of effectively calculable function in the recursion-theoretic tradition, and he proves the equivalence of this class with the λ-definable functions of Church and Kleene. After this paper, “general recursive,” “λ-definable,” and (shortly thereafter) “Turing computable” are known to name the same class of functions — the empirical content of Church’s thesis.

The central technical result is the normal form theorem. Kleene shows that every general recursive function can be written as φ(x) = U(μy. T(e, x, y) = 0), where T is a primitive recursive Kleene T-predicate encoding “y is the Gödel number of a computation of machine/equation-system e on input x,” U is a primitive recursive result-extracting function, and μy. is the unbounded minimisation (least-y) operator. All of the apparent complexity of recursive definitions is thereby pushed into one unbounded search over a primitive-recursive predicate. The theorem provides a canonical form for every partial recursive function — the starting point of computability as a structural theory rather than a list of closure rules.

The paper also clarifies the role of partial functions, introduces the use of indices e as first-class objects (each function gets a Gödel number so one can reason about φ_e), and establishes the technology — T-predicate, μ-operator, index encoding, normal form — that Kleene and others use in every subsequent paper on recursion theory.

Key Ideas

General recursive functions (Herbrand–Gödel equation calculus) adopted as the working definition of effective calculability.
Equivalence with λ-definable functions: Church’s thesis gains an additional leg.
Kleene normal form theorem: every partial recursive function φ_e(x) = U(μy. T(e, x, y) = 0).
T-predicate T(e, x, y): a primitive recursive relation formalising “y codes a computation of e on x.”
μ-operator (unbounded minimisation) as the one non-primitive-recursive ingredient needed.
Indices e for recursive functions — functions become numbers, enabling self-reference and universal machines.

Connections

Conceptual Contribution

Claim: The general recursive functions coincide with the λ-definable functions and admit a single normal form U(μy. T(e, x, y) = 0) reducing all partial recursive computation to unbounded search over a primitive recursive predicate.
Mechanism: Take Herbrand–Gödel equation calculus as primitive. Arithmetise derivations to get a primitive recursive “is-a-computation” predicate T. Use unbounded search (μy) to locate the first terminating computation; extract its result with a primitive recursive U. Cross-simulate with λ-calculus to prove equivalence.
Concepts introduced/used: general recursive function, T-predicate, μ-operator, normal form, index, Recursive Function, Computability
Stance: foundational theorem paper (recursion theory)
Relates to: Second leg (with Church 1936) of Church’s thesis; the normal form becomes the tool by which Kleene 1943 constructs the arithmetical hierarchy and Post 1944 organises r.e. sets; supplies the machinery that Rice 1953 takes for granted.

Foundations of Logic Programming - Lloyd

Foundations of Logic Programming (Chapter 1: Preliminaries)

Reference: J. W. Lloyd (1987). Springer-Verlag, Second Extended Edition. Source file: 2022-08-18 13-38-01-Lloyd.pdf. URL

Summary

The opening chapter of Lloyd’s canonical textbook on the mathematical foundations of logic programming. It introduces first-order theories, syntax (alphabets, terms, well-formed formulas, clauses, Horn clauses), interpretations and models, and Herbrand semantics as the preferred route for reasoning about logical consequence of a program.

Lloyd motivates logic programming as Kowalski’s insight that “algorithm = logic + control”: a definite program is a set of Horn clauses (the logic), and the inference strategy (SLD-resolution, search order) is the control. He distinguishes “system” languages (committed-choice, concurrent) from “application” languages (PROLOG-style), and sets up the semantic machinery — Herbrand interpretations, models, logical consequence, unsatisfiability — needed for the rest of the book.

Key Ideas

Algorithm = Logic + Control (Kowalski’s principle)
Horn clauses as the executable fragment of first-order logic
Herbrand universe and base; Herbrand interpretations suffice for clause sets
Definite programs vs normal programs (negation)
SLD-resolution as refutation procedure (developed in later chapters)

Connections

Conceptual Contribution

Claim: Logic — specifically first-order Horn-clause logic with SLD-resolution — can serve as a programming language, where a program is a set of definite clauses, a computation is resolution refutation, and the declarative semantics (Herbrand models, least fixpoint) coincides with the procedural semantics.
Mechanism: Rigorously build up first-order theories, interpretations, Herbrand interpretations/bases, unification, and the T_P fixpoint operator; prove soundness and completeness of SLD-resolution; develop negation-as-failure, the Closed World Assumption, and semantics of normal programs; treat Prolog as the canonical realisation of the Kowalski slogan “algorithm = logic + control”.
Concepts introduced/used: Logic Programming, Horn Clauses, SLD Resolution, Herbrand Universe, Unification, Negation as Failure, Fixpoint Semantics, Prolog, Closed World Assumption, First-Order Logic, Algorithm = Logic + Control
Stance: formal / foundational textbook
Relates to: Theoretical substrate for Agent-Oriented Programming, ACRE Agent Conversation Reasoning Engine, and Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents (all of which assume BDI agents implemented in logic-programming languages). The mentalistic-semantics side of ACLs (KQML as an Agent Communication Language, FIPA-ACL) presupposes Lloyd-style logical machinery.

Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

Reference: John McCarthy (1960). “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.” Communications of the ACM 3(4): 184-195. (Author-hosted LaTeX reformatting with minor notational changes.) Source file: mccarthy-recursive.pdf. URL

Summary

The Lisp paper. McCarthy describes a programming system — LISP, for LISt Processor — developed for the IBM 704 at MIT, originally designed to support the advice taker of Programs with Common Sense by giving it a substrate for manipulating symbolic (declarative and imperative) sentences. The system evolved into a representation of partial recursive functions over a class of symbolic expressions (S-expressions) whose elegance transcended its motivating application. The paper presents S-expressions, a small set of elementary S-functions (atom, eq, car, cdr, cons), conditional expressions (newly introduced here), recursive function definitions via a λ-calculus-flavored notation, and the universal S-function apply that plays the role of a universal Turing machine and the practical role of an interpreter — the now-iconic code-is-data eval/apply kernel.

The paper then translates this formalism into IBM 704 list structures (the famous CAR/CDR naming reflecting the 704’s address and decrement register fields), describes the main features of the LISP system (garbage collection, interpreter, compiler sketch, free storage), and gives a recursive-function interpretation of flow charts — i.e., a semantics for imperative programs via recursive functions, anticipating much later work on denotational semantics. Conditional expressions, submitted by McCarthy as a letter to CACM and “demoted to a letter” by its editor (notes the footnote), were the notation Algol 60 then rejected in favour of if ... then ... else.

Lisp is simultaneously an AI implementation vehicle and a theory of computation — and the paper’s code-is-data property (programs are S-expressions) is what seeded the Lisp extensibility tradition (macros, embedded DSLs) that later runs through The Extensible Language - Graham, Code as Data, Macros as Language Extension, and Creating Languages in Racket. McCarthy closes promising a Part II on symbolic applications and a companion paper applying the recursive-function formalism to mathematical logic and theorem proving — the latter effectively becoming Correctness of a Compiler for Arithmetic Expressions and Towards a Mathematical Science of Computation.

Key Ideas

S-expressions: uniform tree/list data structure for both programs and data (code-is-data).
Five primitive functions (atom, eq, car, cdr, cons) suffice to define all computable functions over S-expressions.
Conditional expressions (p1 → e1, ..., pn → en) as a first-class construct — introduced to computer science here.
Recursive function definitions and λ-notation for anonymous functions.
Universal function apply — a meta-circular evaluator — plays the role of a universal Turing machine and a working interpreter.
Partial functions are inherent to computation (non-termination) and must be handled explicitly.
Flow charts reinterpreted as recursive function applications — an early denotational-style semantics for imperative programs.
Garbage collection (the concept of automatic reclamation of unreferenced list cells) introduced in the implementation notes.

Connections

Programs with Common Sense — Lisp was originally designed to support the advice taker.
Some Philosophical Problems from the Standpoint of Artificial Intelligence
Epistemological Problems of Artificial Intelligence
Towards a Mathematical Science of Computation — continues the theory-of-computation programme.
Correctness of a Compiler for Arithmetic Expressions — first proof of program correctness uses Lisp-like semantics.
First Order Theories of Individual Concepts and Propositions
Ascribing Mental Qualities to Machines
Circumscription - A Form of Nonmonotonic Reasoning
Generality in Artificial Intelligence
Elephant 2000 - A Programming Language Based on Speech Acts
Common Business Communication Language
The Extensible Language - Graham — Graham’s manifesto for the Lisp extensibility culture.
Code as Data — the homoiconicity principle first made concrete here.
Macros as Language Extension — macros exploit the S-expression representation of programs.
Creating Languages in Racket — modern Racket inherits eval/apply as the DSL substrate.
Lisp
Knowledge Representation
Common Sense Reasoning
An Unsolvable Problem of Elementary Number Theory — Church 1936, the λ-calculus whose notation McCarthy adapts for anonymous functions.
General Recursive Functions of Natural Numbers — Kleene 1936, the partial-recursive-function framing Lisp realises over S-expressions.

Conceptual Contribution

Claim: Partial recursive functions over symbolic expressions can be defined with five primitive operators (atom, eq, car, cdr, cons) plus conditional expressions and recursion, yielding a language in which programs are themselves symbolic expressions and a single universal function apply serves as both a universal Turing machine and a working interpreter — giving a uniform substrate for AI, programming, and the theory of computation.
Mechanism: S-expressions (atomic symbols + dotted pairs, list sugar); five primitives; conditional expression (p → e, ...); recursive function definitions; λ-notation; universal apply(f, args); IBM 704 list-structure implementation; garbage collection; recursive-function semantics of flow charts.
Concepts introduced/used: Lisp, S-expression, Conditional Expression, Recursive Function, Code as Data, Homoiconicity, eval apply, Garbage Collection, Meta-circular Evaluator.
Stance: foundational
Relates to: The implementation substrate that Programs with Common Sense anticipated. Its code-is-data property seeds the extensibility tradition — The Extensible Language - Graham, Macros as Language Extension, Creating Languages in Racket — and its apply formalism is the ancestor of denotational semantics used in Correctness of a Compiler for Arithmetic Expressions and Towards a Mathematical Science of Computation.