通用图灵机：半个世纪的考察
The Universal Turing Machine A Half-Century Survey
Rolf Herken · 初版 1995 年
1人推荐
3位读者提及
4次提及
Alan Turing 于1937年发表的论文《论可计算数及其在判定性问题上的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem），提出了他的论题：任何有效计算都可以编写在诸如被称为 Turing machine 的自动机上。此外，该论文证明了停机问题和一阶逻辑判定问题的不可解性，并提出了通用 Turing machine 的发明。正是这篇文献，被公认为在永恒的视角下标志着“计算机时代”的开端。本书展现了 Turing 的持久影响
Hacker News 上怎么说
正在加载完整评论……
顺便说一句，我也强烈推荐 Robin Gandy 在 1988 年写的优秀论文《The Confluence of Ideas in 1936》，收录于 1995 年的《The Universal Turing Machine A Half-Century Survey》（Rolf Herken 编）[1]（第 51-102 页）。Gandy 详尽地介绍了历史背景，包括 1936 年谁掌握了什么、当时的普遍认知水平，以及大家对 Church 和……的接受程度。
P.S. I also strongly recommend the excellent 1988 paper by Robin Gandy, The Confluence of Ideas in 1936, published in The Universal Turing Machine A Half-Century Survey (ed. Rolf Herken), 1995[1] (pp. 51-102). Gandy gives a full historical background of who knew what in 1936, what the general state of knowledge was at the time, and the reception of both Church's and…
……识别能力。幸运的是，这个预言并未成真，但也仅仅相差一个额外状态而已。[0] Allen Brady，“The Busy Beaver Game and the Meaning of Life”，收录于 Rolf Herken（编）《The Universal Turing Machine: A Half-Century Survey》，牛津大学出版社，1988 年，第 259–277 页。这一章也可以在 Springer 1995 年第 2 版中找到，第 237–254 页。
…powers of recognition. Luckily, this prediction did not come to pass, but only by a margin of one extra state. [0] Allen Brady, "The Busy Beaver Game and the Meaning of Life", in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey, Oxford University Press, 1988, pp. 259–277. This chapter can also be found in the 2nd ed., Springer, 1995, pp. 237–254.
……信息是其发起者合理完成的数学或其他工作的量，而接收者因此免去了重复这些工作的必要。”——Bennett, Charles H.，“Logical depth and physical complexity”，《The Universal Turing Machine: A Half-Century Survey》。
…message is the amount of mathematical or other work plausibly done by its originator, which its receiver is saved from having to repeat." —Bennett, Charles H. "Logical depth and physical complexity." The Universal Turing Machine: A Half-Century Survey.
……https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf [2]：https://mdetlefsen.nd.edu/assets/201037/jf.turing.pdf 即将发表于《Philosophical Explorations of the Legacy of Alan Turing》[3]：http://dl.acm.org/citation.cfm?id=213993 发表在《The Universal Turing Machine A Half Century Survey》（1995年）
…https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf [2]: https://mdetlefsen.nd.edu/assets/201037/jf.turing.pdf to appear in Philosophical Explorations of the Legacy of Alan Turing [3]: http://dl.acm.org/citation.cfm?id=213993 published in The Universal Turing Machine A Half Century Survey, 1995