Ebook: The Universal Turing Machine A Half-Century Survey

"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.

---

"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.
Content:
Front Matter....Pages i-xvi
Front Matter....Pages 1-1
Alan Turing and the Turing Machine....Pages 3-14
Turing’s Analysis of Computability, and Major Applications of It....Pages 15-49
The Confluence of Ideas in 1936....Pages 51-102
Turing in the Land of 0(z)....Pages 103-134
Mathematical Logic and the Origin of Modern Computers....Pages 135-158
Front Matter....Pages 159-159
From Universal Turing Machines to Self-Reproduction....Pages 161-172
Computerizing Mathematics: Logic and Computation....Pages 173-205
Logical Depth and Physical Complexity....Pages 207-235
The Busy Beaver Game and the Meaning of Life....Pages 237-254
An Algebraic Equation for the Halting Probability....Pages 255-259
The Price of Programmability....Pages 261-281
Gandy’s Principles for Mechanisms as a Model of Parallel Computation....Pages 283-288
Influences of Mathematical Logic on Computer Science....Pages 289-299
Language and Computations....Pages 301-321
Finite Physics....Pages 323-347
Randomness, Interactive Proofs, and Zero-Knowledge — A Survey....Pages 349-375
Algorithms in the World of Bounded Resources....Pages 377-385
Beyond the Turing Machine....Pages 387-402
Structure....Pages 403-419
Mental Images and the Architecture of Concepts....Pages 421-432
Front Matter....Pages 159-159
The Fifth Generation’s Unbridged Gap....Pages 433-454
On the Physics and Mathematics of Thought....Pages 455-483
Effective Processes and Natural Law....Pages 485-498
Turing Naturalized: Von Neumann’s Unfinished Project....Pages 499-517
Complexity Theory and Interaction....Pages 519-536
Mechanisms for Computing Over Arbitrary Structures....Pages 537-555
Comparing the Church and Turing Approaches: Two Prophetical Messages....Pages 557-582
Form and Content in Thinking Turing Machines....Pages 583-607
Back Matter....Pages 609-615

---

"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.
Content:
Front Matter....Pages i-xvi
Front Matter....Pages 1-1
Alan Turing and the Turing Machine....Pages 3-14
Turing’s Analysis of Computability, and Major Applications of It....Pages 15-49
The Confluence of Ideas in 1936....Pages 51-102
Turing in the Land of 0(z)....Pages 103-134
Mathematical Logic and the Origin of Modern Computers....Pages 135-158
Front Matter....Pages 159-159
From Universal Turing Machines to Self-Reproduction....Pages 161-172
Computerizing Mathematics: Logic and Computation....Pages 173-205
Logical Depth and Physical Complexity....Pages 207-235
The Busy Beaver Game and the Meaning of Life....Pages 237-254
An Algebraic Equation for the Halting Probability....Pages 255-259
The Price of Programmability....Pages 261-281
Gandy’s Principles for Mechanisms as a Model of Parallel Computation....Pages 283-288
Influences of Mathematical Logic on Computer Science....Pages 289-299
Language and Computations....Pages 301-321
Finite Physics....Pages 323-347
Randomness, Interactive Proofs, and Zero-Knowledge — A Survey....Pages 349-375
Algorithms in the World of Bounded Resources....Pages 377-385
Beyond the Turing Machine....Pages 387-402
Structure....Pages 403-419
Mental Images and the Architecture of Concepts....Pages 421-432
Front Matter....Pages 159-159
The Fifth Generation’s Unbridged Gap....Pages 433-454
On the Physics and Mathematics of Thought....Pages 455-483
Effective Processes and Natural Law....Pages 485-498
Turing Naturalized: Von Neumann’s Unfinished Project....Pages 499-517
Complexity Theory and Interaction....Pages 519-536
Mechanisms for Computing Over Arbitrary Structures....Pages 537-555
Comparing the Church and Turing Approaches: Two Prophetical Messages....Pages 557-582
Form and Content in Thinking Turing Machines....Pages 583-607
Back Matter....Pages 609-615
....