The Universal Turing Machine A Half-Century Survey
by Rolf Herken · first published 1995
4mentions
1recommended by
3HN commenters
2017–2024first – last mentioned
33% recommend67% neutral
"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 T
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
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…
on “Harvey Friedman bringing incompleteness and infinity out of quarantine” ↗…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.
on “With fifth busy beaver, researchers approach computation's limits” ↗…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.
on “Kolmogorov Complexity and Our Search for Meaning” ↗…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
on “Has philosophy ever clarified mathematics?” ↗