Hilbert, Godel, Turing

Hilbert, Gödel e Turing

La nascita del computer va a toccare tre personaggi: Hilbert (inizio 1900), Gödel (anni '30 del 1900) e Turing (nel '36).

David Hilbert e i suoi problemi

Nel 1900, il matematico tedesco David Hilbert, in occasione del primo congresso internazionale dei matematici svoltosi a Parigi, lanciò una sfida ai colleghi di tutto il mondo. Propose ventitré problemi, insoluti da anni o da secoli e da lui giudicati di importanza cruciale. Nel 1928, a Bologna, lo stesso Hilbert rilanciò tre dei problemi formulati trent'anni prima, scelti fra quelli che investivano direttamente i fondamenti, ovvero le basi logiche, di tutta la matematica, e che erano ancora insoluti:

• Quello della completezza
• Quello della coerenza
• Quello della decidibilità

Problema della completezza

Siamo certi che non esistano in matematica enunciati veri ma non dimostrabili?

Problema della coerenza

Come possiamo essere sicuri che la matematica non nasconda contraddizioni fra i suoi assiomi? Come possiamo dimostrare che non accadrà mai di ritrovarsi, partendo da un enunciato vero e compiendo solo passaggi matematici corretti, a un'assurdità del tipo 1+1=0?

Nel 1931, il logico austriaco Gödel chiarì definitivamente i problemi della completezza e della coerenza formulando il suo famoso teorema di incompletezza.

Problema della decidibilità

Esiste sempre una maniera rigorosa di stabilire, cioè di "decidere", se un certo enunciato matematico sia vero o falso?

• 1+1=2 vero o falso?
• 2x5=0 vero o falso?

Congettura di Goldbach e Teorema di Fermat

Nel 1742: congettura di Goldbach, ossia "tutti i numeri interi pari, maggiori di 2, sono la somma di due numeri primi".

• 4=3+1
• 6=5+1
• 8=5+3
• 24=17+7

Come sapere se è vero sempre, per tutti gli infiniti numeri pari che esistono? È ancora non dimostrato oggi.

Un altro famoso teorema è quello di Fermat, del 1637: "Non esistono soluzioni intere positive all'equazione: aⁿ + bⁿ = cⁿ se n>2". Lui non ha dimostrato quello che ha detto, ha appuntato il teorema su un libro, è stato dimostrato solo nel 1994, a quasi quattrocento anni dalla sua formulazione, dal matematico Andrew Wiles.

Alan Turing e il problema della decidibilità

Nel 1936, Alan Turing pubblicò su una rivista matematica inglese un articolo intitolato "On computable numbers, with an application to the Entscheidungsproblem" (sui numeri computabili, con una decidibilità all'Entscheidungsproblem) che risolveva definitivamente anche il problema della decidibilità introducendo l'idea di una macchina astratta, che da lui prese il nome di "macchina di Turing".

Il primo computer elettronico e programmabile si chiamava Colossus. Fu inventato dagli inglesi durante la Seconda Guerra Mondiale per decifrare i messaggi segreti dei nemici tedeschi. Il suo aiuto fu indispensabile per far vincere la guerra agli Alleati. Infatti, quella macchina ogni giorno era in grado di decifrare 4 mila messaggi segreti degli eserciti nemici. È nato quindi prima il concetto del computer e poi la macchina.

Storia del problema della decidibilità

Il problema della decidibilità deriva da un'idea di Leibniz (1646-1716), padre del sistema binario: era convinto che tutti i nostri ragionamenti potessero diventare eseguibili da una macchina (lui è anche stato il padre della calcolatrice).

• Ragione umana ridotta a puro calcolo
• Macchine meccaniche che consentissero l'esecuzione dei calcoli

Friedric Ludwig Gottlob Frege (1848-1925) trova un sistema di regole capace di rendere conto in modo plausibile di tutti i ragionamenti deduttivi umani. Ragionamento deduttivo ossia date delle ipotesi arrivo a una tesi.

Gödel aveva dato man forte nel 1930 a questo discorso di Frege, dicendo che le sue regole fossero complete, ossia senza buchi nella teoria ma era una teoria consistente.

Hilbert cercava anche procedure di calcolo esplicite che, da alcune premesse e una ipotetica conclusione scritte nella notazione di quella che oggi chiamiamo logica del primo ordine (la più bassa, quella del “se” → “allora”), permettessero sempre di stabilire se le regole di Frege consentissero di derivare la seconda dalle prime. Il programma tradizionale degli studi matematici consisteva in buona parte di queste procedure, note anche come algoritmi; i primi algoritmi che impariamo sono l'addizione, la moltiplicazione, la sottrazione e la divisione.

In linea di principio, quindi, l'algoritmo per l'Entscheidungsproblem avrebbe dovuto ridurre tutti i ragionamenti deduttivi umani a calcolo bruto (sogno di Leibniz).