×

A personal account of Turing’s imprint on the development of computer science. (English) Zbl 1298.68017

Summary: The first part of the twentieth century saw the development of the digital computer and the field of computer science. In the present paper, we sketch our vision of that period and of the role that Alan Turing and some of his contemporary peers played in that development.

MSC:

68-03 History of computer science
01A60 History of mathematics in the 20th century
01A70 Biographies, obituaries, personalia, bibliographies
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D10 Turing machines and related notions

Biographic References:

Turing, Alan
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zabell, S. L., Alan Turing and the central limit theorem, American Mathematical Monthly, 102, 6, 483-494 (1995) · Zbl 0833.01016
[2] A.M. Turing, The applications of probability to cryptography, Report, GCHQ, Cheltenham, UK, 1941.; A.M. Turing, The applications of probability to cryptography, Report, GCHQ, Cheltenham, UK, 1941.
[3] A.M. Turing, On statistics of repetitions. Report, GCHQ, Cheltenham, UK, 1941.; A.M. Turing, On statistics of repetitions. Report, GCHQ, Cheltenham, UK, 1941.
[4] Singh, S., The Code Book (2000), Anchor Books
[5] Lewin, R., Ultra Goes to War: The Secret Story (1978), Hutchinson: Hutchinson London
[6] Turing, A. M., Rounding-off errors in matrix processes, The Quarterly Journal of Mechanics and Applied Mathematics, 1, part 3, 287-308 (1948) · Zbl 0033.28501
[7] Cucker, F., The legacy of Turing in numerical analysis, (Bielikova, M.; Friedrich, G.; Gottlob, G.; Katzenbeisser, S.; Turan, G., Proc. SOFSEM. Proc. SOFSEM, Lecture Notes in Computer Science, vol. 7147 (2012), Springer), 1-13 · Zbl 1274.01074
[8] Turing, A. M., Some calculations of the Riemann zeta-function, Proceedings of the London Mathematical Society, 3, 3, 99-117 (1953) · Zbl 0050.08101
[9] Booker, A., Turing and the Riemman hypothesis, Notices of the American Mathematical Society, 53, 10, 1208-1211 (2006) · Zbl 1142.11353
[10] Turing, A. M., Computing machinery and intelligence, MIND, 59, 236, 433-460 (1950)
[11] Turing, A. M., The chemical basis of morphogenesis, Philosophical Transactions of the Real Society of London (Series B), B, 237, 641, 37-72 (1952) · Zbl 1403.92034
[12] Saunders, P. T., Alan Turing and biology, Annals of the History of Computing, 15, 3, 33-36 (1993)
[13] Kidwell, P., Collected works of A. M. Turing — morphogenesis, Annals of the History of Computing, 18, 4, 69 (1996)
[14] Hodges, A., Book Review: the essential Turing, Notices of the ACM, 53, 10, 1190-1199 (2006)
[15] Hodges, A., Alan Turing: The Enigma (1992), Random House · Zbl 0541.68001
[16] Knuth, D. E., Ancient babylonian algorithms, Communications of the ACM, 15, 7, 671-677 (1972) · Zbl 0245.68010
[17] Midonick, H., The Treasury of Mathematics: 1 (1968), Penguin · Zbl 0136.00301
[18] Al-khorezmi, H. Zemanek., (Ershov, A. P.; Knuth, D. E., Algorithms in Modern Mathematics and Computer Science. Algorithms in Modern Mathematics and Computer Science, Lecture Notes in Computer Science, vol. 122 (1980), Springer-Verlag), 1-81
[19] Al-khorezmi, D. E.Knuth., (Ershov, A. P.; Knuth, D., Algorithms in Modern Mathematics and Computer Science. Algorithms in Modern Mathematics and Computer Science, Lecture Notes in Computer Science, vol. 122 (1980), Springer-Verlag), 82-99
[20] Spinellis, D., The Antikythera mechanism: a computer science perspective, Computer, 41, 5, 22-27 (2008)
[21] Cockshott, P.; Mackenzie, L.; Michaelson, G., Computation and its Limits (2012), Oxford University Press · Zbl 1246.68002
[22] M. Davis, The universal computer: the road from Leibniz to Turing, Norton, 2000.; M. Davis, The universal computer: the road from Leibniz to Turing, Norton, 2000. · Zbl 0960.01001
[23] Dyson, G., Turing’s Cathedral (2012), Random House · Zbl 1334.68005
[24] Sales, T., Llull as computer scientist, (Fidora, A.; Sierra, C., Ramon Llull: From the Ars Magna to Artificial Intelligence (2011), IIA-CSIC), 25-37
[25] Bonner, A., The art and logic of Ramon Llull (2007), Brill Academic Publishing
[26] (Heijenoort, J. V., From Frege to Gödel: A Source Book in Mathematical Logic (1967), Harvard University) · Zbl 0183.00601
[27] A. Doxiadis, C. Papadimitriou, A. Papadatos, A. di Donna, LOGICOMIX: an epic search for truth, Bloomsbury, 2009.; A. Doxiadis, C. Papadimitriou, A. Papadatos, A. di Donna, LOGICOMIX: an epic search for truth, Bloomsbury, 2009.
[28] Whitehead, A.; Russell, B., Principia mathematica (1927), Cambridge University Press · JFM 53.0038.02
[29] Hofstadter, D., Gödel, Escher, Bach: An Eternal Golden Braid (1979), Basic Books · Zbl 1014.03005
[30] Grier, D., When Computers Were Human (2005), Princenton University Press
[31] C. Babbage, Passages from the Life of a Philosopher, Cambridge Library Collection, 2011.; C. Babbage, Passages from the Life of a Philosopher, Cambridge Library Collection, 2011.
[32] Lindgren, M., Glory and Failure: The Difference Engines of Johann Muller, Charles Babbage and Georg and Edvard Scheutz (1990), MIT Press
[33] D. Swade, The cogwheel brain. Abacus, 2000.; D. Swade, The cogwheel brain. Abacus, 2000.
[34] D. Swade, The Difference Engine: Charles Babbage and the Quest to Build the First Computer, Penguin, 2002.; D. Swade, The Difference Engine: Charles Babbage and the Quest to Build the First Computer, Penguin, 2002. · Zbl 1017.01006
[35] J. Walker, Babbage machines, http://www.fourmilab.ch/babbage; J. Walker, Babbage machines, http://www.fourmilab.ch/babbage
[36] L. Menabrea, The analytical engine invented by Charles Babbage. Technical report, http://www.fourmilab.ch/babbage/sketch.html; L. Menabrea, The analytical engine invented by Charles Babbage. Technical report, http://www.fourmilab.ch/babbage/sketch.html
[37] Wilkes, M. V., Babbage as a computer pioneer, Historia Mathematica, 4, 4, 415-440 (1977) · Zbl 0379.01006
[38] Bromley, A. G., Charles Babbage’s analytical engine, 1838, Annals of the History of Computing, 4, 3, 196-217 (1982) · Zbl 0998.01507
[39] Coriolis, G.-G., Note sur un moyen de tracer des courbes donns per des equations differentielles, Journal de Mathematiques Pures et Appliqus, 1, 5-9 (1836)
[40] Randell, B., From analytical engine to electronic digital computer: the contributions of ludgate, torres, and bush, Annals of the History of Computing, 4, 4, 327-341 (1982) · Zbl 0998.01508
[41] Ludgate, P., On a proposed analytical machine, Scientific Proceedings of Royal Dublin Society, 12, 9, 77-91 (1909)
[42] Torres-Quevedo, L., Ensayos sobre automatica-su definicion. extension teorica de sus aplicaciones, Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales, 12, 391-418 (1913)
[43] Thomas, F., A short account of Leonardo Torres’ endless spindle, Mechanism and Machine Theory, 43, 8, 1055-1063 (2008) · Zbl 1188.01012
[44] Cohen, B., Babbage and Aiken, Annals of the History of Computing, 33, 1, 22-37 (2011)
[45] Reid, C., Hilbert (1996), Springer · Zbl 0849.01032
[46] Hilbert, D.; Ackermann, W., Grundzüge der Theoretischen Logik (1928), Julius Springer · JFM 54.0055.01
[47] Hilbert, D., Mathematical problems, Bulletin of the American Mathematical Society, 8(, 10, 437-479 (1970) · JFM 33.0976.07
[48] Macrae, N., The Scientific Genius Who Pioneered the Modern Computer, Game Theory, Nuclear Deterrence, and Much More (1999), American Mathematical Society · Zbl 0957.01027
[49] Dawson, J. W., Logical Dilemmas: The Life and Work of Kurt Godel (1996), AK Peters · Zbl 0866.03003
[50] Gödel, K., Uber formal unentscheidbare satze der principia mathematica und verwandter systeme, Monatshefte fur Mathematik und Physik, 38, 173-198 (1931) · JFM 57.0054.02
[51] Meltzer, B., On Formally Undecidable Propositions of Principia Mathematica and Related Systems. Translation of the German original by Kurt Godel (1992), Dover
[52] Nagel, E.; Newman, J. R., Gödel’s Proof (1989), Routledge · Zbl 0086.24602
[53] Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society-2, 42, 230-265 (1936) · Zbl 0016.09701
[54] Church, A., A note on the Entscheidungsproblem, Journal of Symbolic Logic, 1, 1, 40-41 (1936) · JFM 62.1058.04
[55] Turing, A. M., Computability and lambda-definability, Journal of Symbolic Logic, 2, 4, 153-163 (1937) · JFM 63.0824.03
[56] Soare, R. I., Turing and Michelangelo: the art of classical computability, (Cooper, B.; van Leewen, J., Alan Turing-His work and impact (2012), Elsevier), 182-199
[57] Soare, R. I., Turing computability and information content, Philosophical Transactions of the Royal Society, A370, 3277-3304 (2012) · Zbl 1338.03075
[58] Turing, A. M., Systems of logic based on ordinals, Proceedings of the London Mathematical Society-2, 45, 161-228 (1939) · Zbl 0021.09704
[59] T. Oliveira, Goldbach’s conjecture verification. http://www.ieeta.pt/ tos/goldbach.html; T. Oliveira, Goldbach’s conjecture verification. http://www.ieeta.pt/ tos/goldbach.html
[60] Doxiadis, A., Uncle Petros and Goldbach’s Conjecture (2001), Bloomsbury · Zbl 0981.01017
[61] Rogers, H., Theory of Recursive Functions and Effective Computability (1987), MIT Press · Zbl 0183.01401
[62] Balcazar, J. L.; Díaz, J.; Gabarró, J., Structural Complexity, vol. I (1990), Springer-Verlag
[63] Post, E. L., Degrees of recursive unsolvability: preliminary report, Bulletin of the American Mathematical Society, 54, 641-642 (1948)
[64] Kleene, S. C.; Post, E. L., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, 59, 379-407 (1954) · Zbl 0057.24703
[65] Stillwell, J., Emil Post and his anticipation of Godel and Turing, Mathematics Magazine, 77, 1, 3-14 (2004) · Zbl 1112.01308
[66] Stillwell, J., Roads to Infinite: The Mathematics of Truth and Proof (2010), AK Peters · Zbl 1196.00004
[67] de Mol, L., Closing the circle: an analysis of Emil Post’s early work, The Bulletin of Symbolic Logic, 12, 2, 267-289 (2006) · Zbl 1120.03001
[68] Davis, M., The Undecidable (1965), Raven Press
[69] Moore, C.; Mertens, S., The Nature of Computation (2011), Oxford University Press · Zbl 1237.68004
[70] Harmanis, J., Gödel, von Neumann and the P=NP problem, Bulletin of the European Association for Theoretical Computer Science, 38, 101-107 (1989)
[71] Davis, M., Solvability, provability, definability: The collected works of Emil L. Post (1994), Birkhauser · Zbl 0823.03001
[72] Post, E. L., Formal reductions of the general combinatorial decision problem, American Journal of Mathematics, 65, 197-215 (1943) · Zbl 0063.06327
[73] Post, E. L., A variant of a recursively unsolvable problem, Bulletin of the American Mathematical Society, 52, 264-268 (1946) · Zbl 0063.06329
[74] Post, E. L., Recursively enumerable sets of positive integers and their decision problem, Bulletin of the American Mathematical Society, 50, 284-316 (1944) · Zbl 0063.06328
[75] J. Smiley, The man who invented the computer: the biography of John Atanasoff, digital pioneer, 2010.; J. Smiley, The man who invented the computer: the biography of John Atanasoff, digital pioneer, 2010.
[76] Copeland, J., Colossus: The Secrets of Bletchley Park’s Codebreaking Computers (2006), Oxford University Press
[77] J. von Neumann, The first draft of a report on the EDVAC. http://qss.stanford.edu/ godfrey/vonNeumann/vnedvac.pdf; J. von Neumann, The first draft of a report on the EDVAC. http://qss.stanford.edu/ godfrey/vonNeumann/vnedvac.pdf
[78] Godfrey, M. D.; Hendry, D. F., The computer as von Neumann planned it, Annals of the History of Computing, 15, 11-21 (1993) · Zbl 0944.01508
[79] A.M. Turing, Proposal for development in the Mathematics Division of an Automatic Computing Engine (ACE). Report E.882, Executive Committee, inst-NPL, 1945.; A.M. Turing, Proposal for development in the Mathematics Division of an Automatic Computing Engine (ACE). Report E.882, Executive Committee, inst-NPL, 1945.
[80] Carpenter, B.; Doran, R., The other Turing machine, The Computer Journal, 20, 3, 279-296 (1977) · Zbl 0362.68083
[81] Wilkinson, J. H., Turing’s work at the National Physical Laboratory and the construction of Pilot ACE, DEUCE, and ACE, (Metropolis, N.; Howlett, J.; Rota, G.-C., A History of Computing in the Twentieth Century: A Collection of Essays (1980), Academic Press), 101-114
[82] Morris, F. L.; Jones, C. B., An early program proof by Alan Turing, Annals of the History of Computers, 6, 2, 139-143 (1984) · Zbl 0998.01521
[83] S. Aaronson, NP-complete problems and physical reality. Technical Report arXiv:quant-ph/0502072v2; S. Aaronson, NP-complete problems and physical reality. Technical Report arXiv:quant-ph/0502072v2
[84] S. Aaronson, J. Watrous, Closed timelike curves make quantum and classical computing equivalent, Technical Report arXiv:quant-ph/0808.2669; S. Aaronson, J. Watrous, Closed timelike curves make quantum and classical computing equivalent, Technical Report arXiv:quant-ph/0808.2669 · Zbl 1186.81035
[85] Davis, M., Why there is no such discipline as hypercomputation, Applied Mathematics and Computation, 178, 4-7 (2006) · Zbl 1103.68555
[86] 2012 the Alan Turing year. http://www.mathcomp.leeds.ac.uk/turing2012/; 2012 the Alan Turing year. http://www.mathcomp.leeds.ac.uk/turing2012/
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.