The Universal Turing Machine
A Half-century Survey
Published on 1. September 1988
Book
Hardback
674 pages
978-0-19-853741-0 (ISBN)
Description
This volume commemorates the work of Alan Turing, because it was Turing who not only introduced the most persuasive and influential concept of a machine model of effective computability but who also anticipated in his work the diversity of topics brought together here. As Newman put it in his memoir of Turing, "The central problem with which he started and to which he constantly returned is the extent and the limitations of mechanistic explanations of nature." Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" appeared in print in 1937. It contained Turing's thesis that every 'effective' computation can be programmed on a Turing machine. Furthermore, it contained the unsolvability of the halting problem and of the decision problem for first-order logic, and it presented the invention of the universal Turing machine. The publication of this idea is acknowledged as a landmark of the computer age. Part 1 of the volume explores the historical aspect with essays on the background, on Turing's work, and on subsequent developments.
Part 2 contains an extensive series of essays on the influence and applications of these ideas in mathematics, mathematical logic, philosophy of mathematics, computer science, artificial intelligence, philosophy of language, philosophy of mind, and physics. Anyone interested in Turing and his ideas; Computer scientists, logicians, mathematicians, AI researchers, physicists, and other scientists; Historians of mathematics, computing, and science; Philosophers.
Part 2 contains an extensive series of essays on the influence and applications of these ideas in mathematics, mathematical logic, philosophy of mathematics, computer science, artificial intelligence, philosophy of language, philosophy of mind, and physics. Anyone interested in Turing and his ideas; Computer scientists, logicians, mathematicians, AI researchers, physicists, and other scientists; Historians of mathematics, computing, and science; Philosophers.
More details
Language
English
Place of publication
Oxford
United Kingdom
Target group
College/higher education
Professional and scholarly
Illustrations
21 figures
Dimensions
Height: 250 mm
Width: 160 mm
Weight
1080 gr
ISBN-13
978-0-19-853741-0 (9780198537410)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Content
List of contributors; Preface; PART 1: A. Hodges: Alan Turing and the Turing Machine; S.C. Kleene: Turing's analysis of computability, and major applications of it; R. Gandy: The confluence of ideas in 1936; S. Feferman: Turing in the Land of O(z); M. Davis: Mathematical logic and the origin of modern computing. PART 2: M.A. Arbib: From universal Turing machines to self-reproduction; M.J. Beeson: Computerizing mathematics: Logic and computation; C.H. Bennett: Logical depth and physical complexity; A.H. Brady: The busy beaver game and the meaning of life; G.J. Chaitin: An algebraic equation for the halting probability; M. Conrad: The price of programmability; E. Dahlhaus & J.A. Makowsky: Gandy's principles for mechanisms as a model of parallel computation; M. Davis: Influences of mathematical logic on computer science; J.E. Fenstad: Language and computations; D. Finkelstein: Finite physics; O. Goldreich: Randomness, interactive proofs, and zero-knowledge - a survey; Y. Gurevich: Algorithms in the world of bounded resources; B. Hasslacher: Beyond the Turing machine; M. Koppel: Structure; J.A. Makowsky: Mental images and the architecture of concepts; D. Michie: The fifth generation's unbridged gap; R. Penrose: On the physics and mathematics of thought; R. Rosen: Effective processes and natural law; H. Schnelle: Turing naturalized: Von Neumann's unfinished project; U. Sch ning: Complexity theory and interaction; J.C. Shepherdson: Mechanisms for computing over arbitrary structures; B.A. Trakhtenbrot: Comparing the Church and Turing approaches: two prophetical messages; O. Wiener: Form and content in thinking Turing machines; Appendix.