The Universal Turing Machine • A Half-Century Survey

The Universal Turing Machine • A Half-Century Survey

Edited by Rolf Herken
Second Edition

On Computable Numbers, with an Application to the Entscheidungsproblem Alan Turing's paper of 1937, contained his thesis that every effective computation can be programmed on such an automation as that called Turing machine. Furthermore it proved 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. It is that publication that will presumably be acknowledged as marking sub specie aeternitatis the beginning of the "computer age" This volume recognizes the still continuing influence of the Turing machine concept by collecting contributions from international specialists in logic, computability, mathematics, biology, physics, linguistics, and cognitive science, thus signalling the exceptionally wide scope of that concept.


Table of Contents
Part I
Alan Turing and the Turing Machine / Andrew Hodges
Turing's Analysis of Computability, and Major Applications of It / Stephen C. Kleene
The Confluence of Ideas in 1936 / Robin Gandy
Turing in the Land of O(z) / Solomon Feferman --
Mathematical Logic and the Origin of Modern Computing / Martin Davis
Part II
From Universal Turing Machines to Self-Reproduction / Michael A. Arbib
Computerizing Mathematics: Logic and Computation / Michael J. Beeson
Logical Depth and Physical Complexity / Charles H. Bennett
The Busy Beaver Game and the Meaning of Life / Allen H. Brady
An Algebraic Equation for the Halting Probability / Gregory J. Chaitin
The Price of Programmability / Michael Conrad
Gandy's Principles for Mechanisms as a Model of Parallel Computation / Elias Dahlhaus and Johann A. Makowsky
Influences of Mathematical Logic on Computer Science / Martin Davis
Language and Computations / Jens Erik Fenstad
Finite Physics / David Finkelstein
Randomness, Interactive Proofs, and Zero-Knowledge
A Survey / Oded Goldreich
Algorithms in the World of Bounded Resources / Yuri Gurevich
Beyond the Turing Machine / Brosl Hasslacher
Structure / Moshe Koppel
Mental Images and the Architecture of Concepts / Johann A. Makowsky
The Fifth Generation's Unbridged Gap / Donald Michie
On the Physics and Mathematics of Thought / Roger Penrose
Effective Processes and Natural Law / Robert Rosen
Turing Naturalized: Von Neumann's Unfinished Project / Helmut Schnelle
Complexity Theory and Interaction / Uwe Schoning
Mechanisms for Computing Over Arbitrary Structures / John C. Shepherdson
Comparing the Church and Turing Approaches: Two Prophetical Messages / Boris A. Trakhtenbrot
Form and Content in Thinking Turing Machines / Oswald Wiener
Appendix


Springer, Computerkultur II, Paperback, english, 632 pages