---
title: "Computability and λ-Definability"
authors:
  - "Alan M. Turing"
year: 1937
venue: "Journal of Symbolic Logic"
arxiv: null
doi: "10.2307/2268280"
source: "https://doi.org/10.2307/2268280"
topics:
  - church-turing-thesis
  - lambda-calculus
  - turing
seed_rank: 517
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 10
lineage: foundations-of-computing
cites:
  - 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: "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: "Review of Turing: On Computable Numbers (Church–Turing thesis framing)"
    url: "https://www.jstor.org/stable/2268810"
    year: 1937
    arxiv: null
    doi: "10.2307/2268810"
see:
  - "515-on-computable-numbers-with-an-application-to-the-entscheidun"
  - "507-an-unsolvable-problem-of-elementary-number-theory"
  - "526-lambda-definability-and-recursiveness"
  - "514-review-of-turing-on-computable-numbers-church-turing-thesis-"
---

# Computability and λ-Definability

## One-sentence takeaway

Turing proves a function of natural numbers is computable by an a-machine if and only if it is λ-definable.

## Why it matters here

The equivalence theorem Broadside should cite when it says "Turing = Church." Church's review *names* the identification; this paper *proves* both simulations, which is what lets ano treat λ-terms and machine models as interchangeable semantics.

## Key ideas

- Constructs, for each Turing machine, a λ-term that represents its computed function, and conversely compiles each λ-definable function into an a-machine.
- Together with Kleene's λ ↔ general-recursive proof, makes effective calculability look absolute rather than notation-relative.
- Companion to Church's 1937 review; do not confuse this JSL paper with the PLMS computable-numbers article.

## Caveats

## Links

- DOI: [10.2307/2268280](https://doi.org/10.2307/2268280)
- JSTOR: https://www.jstor.org/stable/2268280