moinsen / Software historyDE ↗
← 1936

Event

Turing beschreibt eine universelle Rechenmaschine

Context and research status
  • Kennung: 1936-turing-universelle-maschine
  • Zeitraum: 1936
  • Datumsgenauigkeit: Jahr / year
  • Art: historische Entwicklung / historical development
  • Kategorien: Technik, Akteure, Ereignisse
  • Region: Großbritannien / Britain
  • Beteiligte: Alan Turing: Autor / author

Alan Turing’s paper on computable numbers was received on 28 May 1936 and bears the note “Read 12 November, 1936”. This does not establish a presentation by Turing in person; according to Jack Copeland he was in the United States in November. It describes a universal machine that can process descriptions of other machines.

The model works with symbols on a tape and a machine configuration. Turing’s universal machine receives a description of another machine on its tape and produces the same sequence. This is a conceptual model of computation, not evidence that an electronic computer was built in 1936. Original paper, sections 2 and 6

How does such a model work? It examines one tape square at a time. Its state and the symbol there determine the next step: for example, writing or erasing a symbol, or moving to an adjacent square. Turing first gives a specific machine that produces the sequence 010101…. He describes the universal machine separately; it can process descriptions of different machines. Original paper, sections 1, 3 and 6

Turing also asks whether a general procedure can decide for every machine if it produces infinitely many output symbols. He shows that no such general procedure exists. A machine that keeps moving but produces no further output symbols is treated differently from one producing endless output. This is related to later questions about limits of programs, but is not simply the modern formulation of the halting problem. Original paper, sections 2 and 8

Sources