In 1936, when he was just twenty-four years old, Alan Turing wrote a remarkable paper in which he outlined the theory of computation, laying out the ideas that underlie all modern computers. This groundbreaking and powerful theory now forms the basis of computer science. In Turing’s Vision, Chris Bernhardt explains the theory, Turing’s most important contribution, for the gener...
In 1936, when he was just twenty-four years old, Alan Turing wrote a remarkable paper in which he outlined the theory of computation, laying out the ideas that underlie all modern computers. This groundbreaking and powerful theory now forms the basis of computer science. In Turing’s Vision, Chris Bernhardt explains the theory, Turing’s most important contribution, for the general reader. Bernhardt argues that the strength of Turing’s theory is its simplicity, and that, explained in a straightforward manner, it is eminently understandable by the non-specialist. As Marvin Minsky writes, “The sheer simplicity of the theory’s foundation and extraordinary short path from this foundation to its logical and surprising conclusions give the theory a mathematical beauty that alone guarantees it a permanent place in computer theory.” Bernhardt begins with the foundation and systematically builds to the surprising conclusions. He also views Turing’s theory in the context of mathematical history, other views of computation (including those of Alonzo Church), Turing’s later work, and the birth of the modern computer.
In the paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Turing thinks carefully about how humans perform computation, breaking it down into a sequence of steps, and then constructs theoretical machines capable of performing each step. Turing wanted to show that there were problems that were beyond any computer's ability to solve; in particular, he wanted to find a decision problem that he could prove was undecidable. To explain Turing’s ideas, Bernhardt examines three well-known decision problems to explore the concept of undecidability; investigates theoretical computing machines, including Turing machines; explains universal machines; and proves that certain problems are undecidable, including Turing’s problem concerning computable numbers.
作者简介
· · · · · ·
Chris Bernhardt is Professor of Mathematics at Fairfield University and the author of Turing's Vision: The Birth of Computer Science (MIT Press).
我强调图灵论文如何优雅,实际上仍然是相当难阅读的论文,学生们看到的是图灵想法的当代简化版。1958年,马丁·戴维斯(Martin Davis)根据自己在伊利诺伊大学教授的课程出版了《可计算性与不可解性》(Computabilit0 and Unsolvability)一书。1967年,麻省理工学院人工智能实验室联合创始人马文·明斯基根据当时在麻省理工学院教授的一门课程,出版了《计算:有限和无限机器》(Computation:Finite and Infinite Machines)一书。这两本书有着极大的影响力,它们以一种更简单易懂的方式呈现了图灵的想法,它们让计算理论的研究成为计算机科学的一部分,也让计算机科学发展成了一个独立的学科。 (查看原文)
1 有用 skymonkey 2018-10-04 17:46:09
英文版,不算很厚。从夏天开始读,断断续续地,总算在秋叶开始飘零时读完。作者是数学教授,所以内容也就比较专业,不是糖水科普一路。这个世界的真相,毕竟是数学啊!