---
title: "A Note on the Entscheidungsproblem"
authors:
  - "Alonzo Church"
year: 1936
venue: "Journal of Symbolic Logic"
arxiv: null
doi: "10.2307/2268565"
source: "https://doi.org/10.2307/2268565"
topics:
  - entscheidungsproblem
  - undecidability
  - church
seed_rank: 508
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: "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: "Grundzüge der theoretischen Logik"
    url: "https://link.springer.com/book/10.1007/978-3-642-86848-1"
    year: 1928
    arxiv: null
    doi: "10.1007/978-3-642-86848-1"
  - title: "Correction to A Note on the Entscheidungsproblem"
    url: "https://doi.org/10.2307/2268319"
    year: 1936
    arxiv: null
    doi: "10.2307/2268319"
see:
  - "507-an-unsolvable-problem-of-elementary-number-theory"
  - "515-on-computable-numbers-with-an-application-to-the-entscheidun"
  - "491-grundzuge-der-theoretischen-logik"
  - "509-correction-to-a-note-on-the-entscheidungsproblem"
---

# A Note on the Entscheidungsproblem

## One-sentence takeaway

Church's short JSL note is the form in which "first-order validity is undecidable" entered the logic literature.

## Why it matters here

Companion to the longer AJM paper: when Broadside or an Anoptic verifier says a standing-rule fragment is undecidable, this is the crisp primary cite, not a textbook restatement.

## Key ideas

- Direct statement that there is no recursive procedure deciding validity in the restricted functional calculus.
- Uses λ-definability / effective calculability as developed in the AJM paper.
- Hilbert–Ackermann *Grundzüge* is the target formulation of the Entscheidungsproblem.
- A same-year correction (card 509) patches a gap in the reduction.

## Caveats

## Links

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