Notes to Turing Machines
1. The update to this entry published in September 2018 was initially begun in 2015 by S. Barry Cooper, who died unexpectedly shortly after he began work. His most important change at that time was to sketch some of the points he was planning to discuss in the updated entry. We used these points as a guideline to shape the 2018 update. They can be summarized as follows:
- The description of the algorithmic activity is explicitly aimed at the machine, rather than at an attendant human. And this activity is reduced by Turing to its simplest elements, yielding an honesty about the work done appropriate to the measuring of computational complexity or allowing more general computations of infinite length.
- The role of the data to be manipulated is clear and relatively flexible within the logical structure of the algorithm, a spotlighting appropriate to today’s informational world.
- The focus on a ‘machine’, based on Turing’s modelling of it on the human computer following instructions, makes clearer the dependence of the implementation of abstract computation on the provision of a physical host. And conversely, Turing’s clear description of the modelling and its incorporation of all possibilities, persuaded Gödel and others of the validity of the Church-Turing thesis.
- Turing’s predilection for ingenious programs arose from an early awareness of the flexibility of the balance between computer hardware and software. But it was his description of the program using language representable as data readable by the machine that anticipated the program-as-data paradigm. And the latter led to Turing’s Universal machine (see below), and the theoretical underpinning of John von Neumann’s logical architecture, so important in the history of today’s stored-program computer.
- In Turing 1936–7, the unsolvability of Hilbert’s Entscheidungsproblem becomes more clearly associated with the sampling of collated computable data—clarifying the association of incomputability with descriptions involving the use of quantifiers. The relationship of descriptions using natural language to the underlying computability, or lack of it, is an ongoing area of research and speculation.
We note here that Section 5, was written based on point iv.