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à.
Referenze Bibliografiche
[BG03]
ANDREAS BLASS and
YURI GUREVICH,
Algorithms: A quest for absolute definitions.
Bulletin of the EATCS,
81:195-225,
2003. |
MR 2132778 |
Zbl 1169.68408[Chu36] ALONZO CHURCH, A note on the Entscheidungsproblem. Journal of Symbolic Logic, 1:40-41, 1936. Ristampato in [Dav04].
[Chu56]
ALONZO CHURCH,
Introduction to Mathematical Logic,
Princeton University Press,
1956. |
MR 1435972 |
Zbl 0073.24301[Coo12] S. BARRY COOPER, Turing's titanic machine? Commun. ACM, 55(3):74-83, 2012.
[Dav04]
MARTIN DAVIS, editor.
The Undecidable.
Dover Publications,
2004. |
MR 2070909[EW03]
EUGENE EBERBACH and
PETER WEGNER,
Beyond Turing machines.
Bulletin of the EATCS,
81:279-304,
2003. |
MR 2132782 |
Zbl 1169.68409[For10] LANCE FORTNOW, Ubiquity symposium `What is computation?': The enduring legacy of the Turing machine. Magazine Ubiquity, Article no. 5, December 2010, ACM.
[Göd31]
KURT GÖDEL,
Ü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]. |
fulltext (doi) |
MR 1549910[HMU09] JOHN E. HOPCROFT, RAJEEV MOTWANI, and JEFFREY D. ULLMAN. Automi, linguaggi, e calcolabilità. Pearson, versione italiana a cura di G. Pighizzini, 2009.
[Hod83]
ANDREW HODGES,
Alan Turing: The Enigma.
Burnett Books,
1983. Edizione italiana:
Bollati Boringhieri,
1991. |
MR 882917[Kan92] IMMANUEL KANT, Critica del giudizio Laterza, 1997 (data di pubblicazione originaria: 1892).
[Knu69]
DONALD KNUTH,
The Art of Computer Programming,
Addison Wesley, Vols.
1,
2,
3,
1969-
1973. |
MR 286318[Lei85]
GOTTFRIED WILHELM LEIBNIZ.
Scritti di Logica. A cura di
F. Barone,
Laterza,
1992 (data di pubblicazione originaria:
1685). |
fulltext (doi) |
MR 1191616[MS11] DINO MANDRIOLI and PAOLA SPOLETINI, Informatica Teorica. Città studi edizioni, 2011. II edizione.
[Mar54]
ANDREJ MARKOV,
The Theory of Algorithms,
Transactions of the American Mathematical Society,
2(15): 1-14,
1954. |
fulltext (doi) |
MR 114753[Mat93]
YURI MATIYASEVICH,
Hilbert's 10th Problem,
MIT Press,
1993 |
MR 1247235[Pea81] GIUSEPPE PEANO, Sul concetto di numero, Rivista di Matematica, 1:87-102 e 256-267, 1981
[Sha38] CLAUDE SHANNON, A Symbolic Analysis of Relay and Switching Circuits, Transactions American Institute of Electrical Engineers, 57: 713-723, 1938.
[Sip05]
MICHAEL SIPSER,
Introduction to the Theory of Computation.
Course Technology, 2nd edition,
2005. |
Zbl 1169.68300[Soa09]
ROBERT I. SOARE,
Turing oracle machines, online computing, and three displacements in computability theory.
Annals of Pure and Applied Logic,
160:368-399,
2009. |
fulltext (doi) |
MR 2555785 |
Zbl 1230.03073[Tur34] ALAN M. TURING, On the Gaussian error function. Manoscritto (dissertazione per la fellowship a Cambridge), 1934.
[Tur37]
ALAN M. TURING,
On computable numbers, with an application to the Entscheidungsproblem.
Proceedings of the London Mathematical Society,
42:230-265,
1937. Ristampato in [Dav04]. |
fulltext (doi) |
MR 1577030 |
Zbl 62.1059.03[Tur39]
ALAN M. TURING,
Systems of logic based on ordinals.
Proceedings of the London Mathematical Society,
45,
1939. Tesi di Ph.D. presentata a Princeton, ristampato in [Dav04]. |
fulltext (doi) |
MR 1576807 |
Zbl 65.1102.02[Tur43]
ALAN M. TURING,
A method for the calculation of the Zeta-function.
Proceedings of the London Mathematical Society,
48,
1943. |
fulltext (doi) |
MR 9612[Tur45] ALAN M. TURING, Proposed electronic calculator. (Il ``rapporto ACE'' verrà pubblicato da NPL nel 1972), 1945.
[Tur50a]
ALAN M. TURING,
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. |
fulltext (doi) |
MR 741062[Tur50b]
ALAN M. TURING,
Computing machinery and intelligence.
Mind,
59:433-460,
1950. |
fulltext (doi) |
MR 37064[Tur52]
ALAN M. TURING,
The chemical basis of morphogenesis.
Philosophical Transactions of the Royal Society (B),
237,
1952. |
MR 3363444 |
Zbl 1403.92034[War12]
KEVIN WARWICK,
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. |
fulltext (doi) |
MR 2958169[WG03] PETER WEGNER and DINA Q. GOLDIN, Computation beyond Turing machines. Commun. ACM, 46(4):100-102, 2003.
[WR09] ALFRED NORTH WHITEHEAD and BERTRAND RUSSELL, Principia Mathematica. Merchant Book, 2009. (Pubblicazione originaria: Cambridge University Press, 1910, 1912, 1913; seconda edizione 1925, 1927).
Con il contributo del Ministero per i Beni e le Attività Culturali