Movatterモバイル変換

1. The new version of this entry published in September 2018 wasinfluenced by the work of S. Barry Cooper in 2015. He was going toupdate an older version of the entry, but he died shortly after hebegan work. His most important change at that time was to sketch someof the points he was planning to discuss in an updated entry. We usedthese points as a guideline to shape the 2018 version. They can besummarized as follows:

1. The description of the algorithmic activity is explicitly aimed atthe machine, rather than at an attendant human. And this activity isreduced by Turing to its simplest elements, yielding an honesty aboutthe work done appropriate to the measuring of computational complexityor allowing more general computations of infinite length.
2. The role of the data to be manipulated is clear and relativelyflexible within the logical structure of the algorithm, a spotlightingappropriate to today’s informational world.
3. The focus on a ‘machine’, based on Turing’smodelling of it on thehuman computer following instructions,makes clearer the dependence of the implementation of abstractcomputation on the provision of a physical host. And conversely,Turing’s clear description of the modelling and itsincorporation of all possibilities, persuaded Gödel and others ofthe validity of the Church-Turing thesis.
4. Turing’s predilection for ingenious programs arose from anearly awareness of the flexibility of the balance between computerhardware and software. But it was his description of the program usinglanguage representable as data readable by the machine thatanticipated the program-as-data paradigm. And the latter led toTuring’sUniversal machine (see below), and thetheoretical underpinning of John von Neumann’slogicalarchitecture, so important in the history of today’sstored-program computer.
5. In Turing 1936–7, the unsolvability of Hilbert’sEntscheidungsproblem becomes more clearly associated with thesampling ofcollated computabledata—clarifying the association of incomputability withdescriptions involving the use of quantifiers. The relationship ofdescriptions using natural language to the underlying computability,or lack of it, is an ongoing area of research and speculation.

We note here thatSection 5 was written based on point iv.