---
title: "λ-definability and recursiveness"
authors:
  - "Stephen C. Kleene"
year: 1936
venue: "Duke Mathematical Journal"
arxiv: null
doi: "10.1215/S0012-7094-36-00227-2"
source: "https://doi.org/10.1215/S0012-7094-36-00227-2"
topics:
  - lambda-calculus
  - recursive-functions
  - kleene
seed_rank: 526
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 9
lineage: foundations-of-computing
cites:
  - title: "General recursive functions of natural numbers"
    url: "https://doi.org/10.1007/BF01565439"
    year: 1936
    arxiv: null
    doi: "10.1007/BF01565439"
  - title: "An Unsolvable Problem of Elementary Number Theory"
    url: "https://doi.org/10.2307/2371045"
    year: 1936
    arxiv: null
    doi: "10.2307/2371045"
  - title: "Computability and λ-Definability"
    url: "https://doi.org/10.2307/2268280"
    year: 1937
    arxiv: null
    doi: "10.2307/2268280"
see:
  - "525-general-recursive-functions-of-natural-numbers"
  - "507-an-unsolvable-problem-of-elementary-number-theory"
  - "517-computability-and-lambda-definability"
---

# λ-definability and recursiveness

## One-sentence takeaway

Kleene gives the explicit translations that prove λ-definable functions are exactly the general recursive ones.

## Why it matters here

Technical hinge among Church, Kleene, and later Turing equivalences. When ano treats a λ-combinator as a total (or partial) recursive column transform, this is the paper that licensed the identification.

## Key ideas

- One direction compiles a Herbrand–Gödel equation system into a λ-term; the other extracts an equation system from a λ-definition.
- Together with the *Mathematische Annalen* paper, makes "absolute" effective calculability look independent of the host notation.
- Turing's 1937 JSL paper then adds the machine vertex of the same triangle.

## Caveats

## Links

- DOI: [10.1215/S0012-7094-36-00227-2](https://doi.org/10.1215/S0012-7094-36-00227-2)
- URL: https://doi.org/10.1215/S0012-7094-36-00227-2