The Universal Turing Machine A Half-Century Survey
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This book discusses Alan Turing's analysis of Computability, and major applications of It, and Turing Naturalized: Von Neumann's Unfinished Project.
Abstract
I.- Alan Turing and the Turing Machine.- Turing's Analysis of Computability, and Major Applications of It.- The Confluence of Ideas in 1936.- Turing in the Land of O(z).- Mathematical Logic and the Origin of Modern Computing.- II.- From Universal Turing Machines to Self-Reproduction.- Computerizing Mathematics: Logic and Computation.- Logical Depth and Physical Complexity.- The Busy Beaver Game and the Meaning of Life.- An Algebraic Equation for the Halting Probability.- The Price of Programmability.- Gandy's Principles for Mechanisms as a Model of Parallel Computation.- Influences of Mathematical Logic on Computer Science.- Language and Computations.- Finite Physics.- Randomness, Interactive Proofs, and Zero-Knowledge - A Survey.- Algorithms in the World of Bounded Resources.- Beyond the Turing Machine.- Structure.- Mental Images and the Architecture of Concepts.- The Fifth Generation's Unbridged Gap.- On the Physics and Mathematics of Thought.- Effective Processes and Natural Law.- Turing Naturalized: Von Neumann's Unfinished Project.- Complexity Theory and Interaction.- Mechanisms for Computing Over Arbitrary Structures.- Comparing the Church and Turing Approaches: Two Prophetical Messages.- Form and Content in Thinking Turing Machines.