---
title: "General recursive functions of natural numbers"
authors:
  - "Stephen C. Kleene"
year: 1936
venue: "Mathematische Annalen"
arxiv: null
doi: "10.1007/BF01565439"
source: "https://doi.org/10.1007/BF01565439"
topics:
  - recursive-functions
  - kleene
  - computability
seed_rank: 525
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 10
lineage: foundations-of-computing
cites:
  - title: "An Unsolvable Problem of Elementary Number Theory"
    url: "https://doi.org/10.2307/2371045"
    year: 1936
    arxiv: null
    doi: "10.2307/2371045"
  - title: "λ-definability and recursiveness"
    url: "https://doi.org/10.1215/S0012-7094-36-00227-2"
    year: 1936
    arxiv: null
    doi: "10.1215/S0012-7094-36-00227-2"
  - title: "On Computable Numbers, with an Application to the Entscheidungsproblem"
    url: "https://doi.org/10.1112/plms/s2-42.1.230"
    year: 1936
    arxiv: null
    doi: "10.1112/plms/s2-42.1.230"
  - title: "Finite Combinatory Processes—Formulation I"
    url: "https://doi.org/10.2307/2268534"
    year: 1936
    arxiv: null
    doi: "10.2307/2268534"
see:
  - "507-an-unsolvable-problem-of-elementary-number-theory"
  - "526-lambda-definability-and-recursiveness"
  - "515-on-computable-numbers-with-an-application-to-the-entscheidun"
  - "532-finite-combinatory-processes-formulation-i"
---

# General recursive functions of natural numbers

## One-sentence takeaway

Kleene defines general recursive functions via Herbrand–Gödel equation systems and proves they coincide with Church's λ-definable functions.

## Why it matters here

Third pillar of the 1936 computability cluster, and the algebraic face Anoptic inherits whenever it talks about primitive recursion, μ-recursion, or "this column is a total function of those columns." Proof theory and PL both still quote this definition.

## Key ideas

- A function is general recursive if it is the unique solution of a finite system of equations built from zero, successor, and substitution, allowing a least-number search.
- Equivalence with λ-definability is proved here and amplified in the companion Duke paper (card 526).
- Primitive recursive functions sit strictly inside; the μ-operator is what buys partiality and full computability.
- Together with Church, Turing, and Post 1936, makes "effectively calculable" look notation-independent.

## Caveats

## Links

- DOI: [10.1007/BF01565439](https://doi.org/10.1007/BF01565439)
- URL: https://doi.org/10.1007/BF01565439