---
title: "On Computable Numbers, with an Application to the Entscheidungsproblem"
authors:
  - "Alan M. Turing"
year: 1936
venue: "Proceedings of the London Mathematical Society"
arxiv: null
doi: "10.1112/plms/s2-42.1.230"
source: "https://doi.org/10.1112/plms/s2-42.1.230"
topics:
  - turing-machine
  - computability
  - entscheidungsproblem
  - halting
seed_rank: 515
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: "Computability and λ-Definability"
    url: "https://doi.org/10.2307/2268280"
    year: 1937
    arxiv: null
    doi: "10.2307/2268280"
  - title: "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction"
    url: "https://doi.org/10.1112/plms/s2-43.6.544"
    year: 1937
    arxiv: null
    doi: "10.1112/plms/s2-43.6.544"
  - title: "Finite Combinatory Processes—Formulation I"
    url: "https://doi.org/10.2307/2268534"
    year: 1936
    arxiv: null
    doi: "10.2307/2268534"
  - title: "General recursive functions of natural numbers"
    url: "https://doi.org/10.1007/BF01565439"
    year: 1936
    arxiv: null
    doi: "10.1007/BF01565439"
  - title: "First Draft of a Report on the EDVAC"
    url: "https://web.mit.edu/STS.035/www/PDFs/edvac.pdf"
    year: 1945
    arxiv: null
    doi: "10.5479/sil.538961.39088011475779"
see:
  - "507-an-unsolvable-problem-of-elementary-number-theory"
  - "517-computability-and-lambda-definability"
  - "516-on-computable-numbers-with-an-application-to-the-entscheidun"
  - "532-finite-combinatory-processes-formulation-i"
  - "525-general-recursive-functions-of-natural-numbers"
  - "542-first-draft-of-a-report-on-the-edvac"
---

# On Computable Numbers, with an Application to the Entscheidungsproblem

## One-sentence takeaway

Turing defines computable real numbers via a-machines, builds a universal machine, and proves the Entscheidungsproblem unsolvable by showing that "circle-freeness" is undecidable.

## Why it matters here

The root machine model for every Anoptic simulation, complexity argument, and "what can be computed" claim. Stored-program talk in the EDVAC/ACE cards is this universal machine turned into engineering.

## Key ideas

- An a-machine (automatic machine) has a finite table of behaviour, a scanned square, and an infinite tape of symbols.
- A computable sequence is one printed by a circle-free machine; a computable number is a real whose binary expansion is such a sequence.
- The universal machine \(U\) takes a standard description of any a-machine and simulates it.
- There is no machine that decides, of an arbitrary description, whether the corresponding machine is circle-free; hence first-order validity is undecidable.
- An appendix sketches the relation to Church's λ-definability; the 1937 correction (card 516) fixes details.

## Caveats

## Links

- DOI: [10.1112/plms/s2-42.1.230](https://doi.org/10.1112/plms/s2-42.1.230)
- URL: https://doi.org/10.1112/plms/s2-42.1.230