---
title: "An Unsolvable Problem of Elementary Number Theory"
authors:
  - "Alonzo Church"
year: 1936
venue: "American Journal of Mathematics"
arxiv: null
doi: "10.2307/2371045"
source: "https://doi.org/10.2307/2371045"
topics:
  - lambda-calculus
  - undecidability
  - church-thesis
  - computability
seed_rank: 507
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: "A Note on the Entscheidungsproblem"
    url: "https://doi.org/10.2307/2268565"
    year: 1936
    arxiv: null
    doi: "10.2307/2268565"
  - title: "General recursive functions of natural numbers"
    url: "https://doi.org/10.1007/BF01565439"
    year: 1936
    arxiv: null
    doi: "10.1007/BF01565439"
  - title: "The Calculi of Lambda-Conversion"
    url: "https://press.princeton.edu/books/paperback/9780691083940/the-calculi-of-lambda-conversion"
    year: 1941
    arxiv: null
    doi: null
  - 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"
  - "508-a-note-on-the-entscheidungsproblem"
  - "525-general-recursive-functions-of-natural-numbers"
  - "511-the-calculi-of-lambda-conversion"
  - "514-review-of-turing-on-computable-numbers-church-turing-thesis-"
---

# An Unsolvable Problem of Elementary Number Theory

## One-sentence takeaway

Church identifies effective calculability with λ-definability and proves there is no algorithm for the Entscheidungsproblem of first-order logic.

## Why it matters here

One half of the Church–Turing birth announcement: the other half is Turing's a-machines. Ano still speaks λ, so this is the paper that says "if you can compute it, you can write it as a λ-term"—the semantic mother tongue of every later typed-array and effects card.

## Key ideas

- Effective calculability is defined as λ-definability (Church's thesis, stated as a definition).
- The Entscheidungsproblem—decide validity of an arbitrary first-order formula—is shown unsolvable by reduction to an unsolvable problem about λ-conversion.
- Parallel 1936 result to Turing's PLMS paper, using conversion instead of tape machines.
- The companion JSL note (card 508) restates the unsolvability claim in the form logicians cite.

## Caveats

## Links

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