Turing: la vita, l'opera, l'impatto
Furia, Carlo A. ; Mandrioli, Dino
La Matematica nella Società e nella Cultura. Rivista dell'Unione Matematica Italiana, Tome 5 (2012), p. 105-148 / Harvested from Biblioteca Digitale Italiana di Matematica
Access to full text
Full (PDF)
Full (DjVu)

Scritto in occasione del centenario della nascita, questo articolo ripercorre le tappe fondamentali della vita di Alan Turing mettendone in evidenza i contributi principali e il ruolo egemone nella fondazione dell'informatica moderna. Dopo una sezione iniziale che tratteggia la biografia di Turing e i risultati più importanti, presentiamo in maniera approfondita con un taglio adeguato ad un pubblico con conoscenze matematiche fondamentali ma non specialista in informatica teorica il risultato forse più importante e più conosciuto tra quelli di Turing: quello pubblicato nel 1937 sulla teoria della computabilità che introduce una classe di automi universalmente noti come ``macchine di Turing''. Infine, nella sezione conclusiva,tratteggiamo alcuni aspetti storico/filosofici legati al concetto di computazione e ai suoi limiti intrinseci, mostrando come il contributo di Turing trascenda i limiti della pura speculazione teorica assumendo anche connotati pratici e culturali di portata generale e ancora di grandissima attualità.

Written on the occasion of his birth's 100th anniversary, this article revisits the main steps of Alan Turing's life, and illustrates his fundamental contributions and his preeminent impact in the foundation of modern computer science. After an initial section that outlines Turing's biography and his most important results, we give a detailed presentation tailored to a general public with basic mathematical background but no expertise in theoretical computerscience of what is possibly the most important and best known result of Turing's: his 1937 paper on the theory of computation, which introduces the class of automata known as ``Turing machines''. Finally, in the closing section we offer some historical/philosophical remarks about the notion of computation and its intrinsic limitations; this shows how Turing's contribution goes well beyond the limits of pure theoretical speculation as it carries practical and cultural implications that are general and still markedly relevant to the present time.

Publié le : 2012-08-01
@article{RIUMI_2012_1_5_2_105_0,
     author = {Carlo A. Furia and Dino Mandrioli},
     title = {Turing: la vita, l'opera, l'impatto},
     journal = {La Matematica nella Societ\`a e nella Cultura. Rivista dell'Unione Matematica Italiana},
     volume = {5},
     year = {2012},
     pages = {105-148},
     zbl = {1391.01020},
     mrnumber = {3059947},
     language = {it},
     url = {http://dml.mathdoc.fr/item/RIUMI_2012_1_5_2_105_0}
}

Furia, Carlo A.; Mandrioli, Dino. Turing: la vita, l'opera, l'impatto. La Matematica nella Società e nella Cultura. Rivista dell'Unione Matematica Italiana, Tome 5 (2012) pp. 105-148. http://gdmltest.u-ga.fr/item/RIUMI_2012_1_5_2_105_0/

[BG03] Blass, Andreas and Gurevich, Yuri, Algorithms: A quest for absolute definitions. Bulletin of the EATCS, 81:195-225, 2003. | MR 2132778 | Zbl 1169.68408

[Chu36] Church, Alonzo, A note on the Entscheidungsproblem. Journal of Symbolic Logic, 1:40-41, 1936. Ristampato in [Dav04].

[Chu56] Church, Alonzo, Introduction to Mathematical Logic, Princeton University Press, 1956. | MR 1435972 | Zbl 0073.24301

[Coo12] Barry Cooper, S., Turing's titanic machine?Commun. ACM, 55(3):74-83, 2012.

[Dav04] Martin Davis, editor. The Undecidable. Dover Publications, 2004. | MR 2070909

[EW03] Eberbach, Eugene and Wegner, Peter, Beyond Turing machines. Bulletin of the EATCS, 81:279-304, 2003. | MR 2132782 | Zbl 1169.68409

[For10] Fortnow, Lance, Ubiquity symposium `What is computation?': The enduring legacy of the Turing machine. Magazine Ubiquity, Article no. 5, December 2010, ACM.

[Göd31] Gödel, Kurt, Über formal unentscheidbare sätze der Principia Mathematica und verwandter Systeme. Monatshefte für Mathematik und Physik, 38:173-198, 1931. Ristampato tradotto in inglese in [Dav04]. | MR 1549910

[HMU09] Hopcroft, John E., Motwani, Rajeev, and Ullman, Jeffrey D.. Automi, linguaggi, e calcolabilità. Pearson, versione italiana a cura di G. Pighizzini, 2009.

[Hod83] Hodges, Andrew, Alan Turing: The Enigma. Burnett Books, 1983. Edizione italiana: Bollati Boringhieri, 1991. | MR 882917

[Kan92] Kant, Immanuel, Critica del giudizioLaterza, 1997 (data di pubblicazione originaria: 1892).

[Knu69] Knuth, Donald, The Art of Computer Programming, Addison Wesley, Vols. 1, 2, 3, 1969-1973. | MR 286318

[Lei85] Wilhelm Leibniz, Gottfried. Scritti di Logica. A cura di F. Barone, Laterza, 1992 (data di pubblicazione originaria: 1685). | MR 1191616

[MS11] Mandrioli, Dino and Spoletini, Paola, Informatica Teorica. Città studi edizioni, 2011. II edizione.

[Mar54] Markov, Andrej, The Theory of Algorithms, Transactions of the American Mathematical Society, 2(15): 1-14, 1954. | MR 114753

[Mat93] Matiyasevich, Yuri, Hilbert's 10th Problem, MIT Press, 1993 | MR 1247235

[Pea81] Peano, Giuseppe, Sul concetto di numero, Rivista di Matematica, 1:87-102 e 256-267, 1981

[Sha38] Shannon, Claude, A Symbolic Analysis of Relay and Switching Circuits, Transactions American Institute of Electrical Engineers, 57: 713-723, 1938.

[Sip05] Sipser, Michael, Introduction to the Theory of Computation. Course Technology, 2nd edition, 2005. | Zbl 1169.68300

[Soa09] Soare, Robert I., Turing oracle machines, online computing, and three displacements in computability theory. Annals of Pure and Applied Logic, 160:368-399, 2009. | MR 2555785 | Zbl 1230.03073

[Tur34] Turing, Alan M., On the Gaussian error function. Manoscritto (dissertazione per la fellowship a Cambridge), 1934.

[Tur37] Turing, Alan M., On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230-265, 1937. Ristampato in [Dav04]. | MR 1577030 | Zbl 62.1059.03

[Tur39] Turing, Alan M., Systems of logic based on ordinals. Proceedings of the London Mathematical Society, 45, 1939. Tesi di Ph.D. presentata a Princeton, ristampato in [Dav04]. | MR 1576807 | Zbl 65.1102.02

[Tur43] Turing, Alan M., A method for the calculation of the Zeta-function. Proceedings of the London Mathematical Society, 48, 1943. | MR 9612

[Tur45] Turing, Alan M., Proposed electronic calculator. (Il ``rapporto ACE'' verrà pubblicato da NPL nel 1972), 1945.

[Tur48] Turing, Alan M., Rounding-off errors in matrix processes. Quarterly Journal of Mechanics and Applied Mathematics, 1, 1948. | MR 28100 | Zbl 0033.28501

[Tur50a] Turing, Alan M., Checking a large routine. Technical report, Cambridge Mathematical Laboratory, 1950. Apparso in ``Annals of the History of Computing'', vol. 6, 1984, a cura di F.L. Morris e C.B. Jones. | MR 741062

[Tur50b] Turing, Alan M., Computing machinery and intelligence. Mind, 59:433-460, 1950. | MR 37064

[Tur52] Turing, Alan M., The chemical basis of morphogenesis. Philosophical Transactions of the Royal Society (B), 237, 1952. | MR 3363444 | Zbl 1403.92034

[War12] Warwick, Kevin, Not another look at the Turing test! In SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science. Proceedings, volume 7147 of Lecture Notes in Computer Science, pages 130-140. Springer, 2012. | MR 2958169

[WG03] Wegner, Peter and Goldin, Dina Q., Computation beyond Turing machines. Commun. ACM, 46(4):100-102, 2003.

[WR09] North Whitehead, Alfred and Russell, Bertrand, Principia Mathematica. Merchant Book, 2009. (Pubblicazione originaria: Cambridge University Press, 1910, 1912, 1913; seconda edizione 1925, 1927).