Hilbert, Godel, Turing

Teoremi matematici famosi

Nel 1742: congettura di Golbach, 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: a^n + b^n = c^n "non esistono soluzioni intere positive all'equazione 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.

Problema della decidibilità HILBERT - GODEL - TURING

Nel 1936 Alan Turing pubblicò su una rivista matematica inglese un articolo intitolato "on computable numbers, with an application to the entscheidungsproblem" (su 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. 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 direndere conto in modo plausibile di tutti iragionamenti deduttivi umani. Il ragionamento deduttivo consiste nel partire da delle ipotesi e arrivare ad una tesi. Nel 1930, Godel ha supportato questo discorso di Frege affermando che le sue regole erano complete, ossia non presentavano buchi nella teoria, ma era una teoria consistente. Hilbert cercava anche procedure di calcolo esplicite che, partendo 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'Entscheidungsproblemavrebbe dovuto ridurre tutti i ragionamenti deduttivi umani a calcolo bruto (sogno di Leibniz). I matematici affrontano un problema difficile da due direzioni: risolvere casi particolari del problema generale, ridurre il problema generale ai casi particolari. Se tutto va bene, i due approcci si incontrano a metà strada, formando una soluzione del problema generale. La ricerca sull'Entscheidungsproblem procedeva lungo queste due direzioni. La lacuna fra: casi particolari, casi ai quali era stato ridotto il problema generale, mancava pochissimo per colmarla per intero. G.H.Hardy (1877-1947) diceva: "se l'algoritmo cercato da Hilbert esistesse, potremmo disporre di un insieme di regole meccaniche per la soluzione di tutti i problemi matematici, il che porrebbe fine alla nostra attività come matematici". L'anno dopo arriva il teorema dell'incompletezza che dà la mazzata finale: dopo il teorema di incompletezza di Godel è difficile pensare che potesse esistere.

unalgoritmo come quello cercato da Hilbert. Turing cominciò a chiedersi come sipoteva dimostrare che un algoritmo del genere non esistevaHILBERT - GODEL - TURING 4non tutti i numeri sono computabili, cisono alcuni numeri che non sonocomputabili, tipo pi greco.se c'è una macchina che è un grado discrivere 1+1=2 allora 2 è scrivibile inmodo computabile.scopo è quello di dimostrare che ilproblema della decidibilità non hasoluzioni. Quindi il computer nasce inmodo accidentale, dimostrando unacosa che non il computer in apparenzanon centra nulla, ossia il problema delladecidibilità.HILBERT - GODEL - TURING 5macchina a statila macchina si muove a step, perquesto si chiama a-machine (automaticmachine)HILBERT - GODEL - TURING 6fa uso di 0 e 1, prende in prestitosistema binarioTuring sapeva che un algoritmo è un insieme di regole che una persona può seguirein modo meccanico e preciso, ma spostò la sua attenzione dalle

regole a quello che la persona effettivamente faceva, eliminando i dettagli inessenziali. Dimostrando che: una tale persona poteva limitarsi a poche azioni di base; l'essere umano poteva essere sostituito da una macchina capace di eseguire quelle stesse azioni di base; dimostrò che nessuna macchina in grado di eseguire solo tali azioni poteva stabilire se una data conclusione era derivabile da premesse date usando le regole di Frege; come corollario trovò un modello matematico di macchina calcolatrice onnifunzionale. Immaginiamo di assistere all'esecuzione di un calcolo 4231 x 77 con un nastro di carta diviso in quadretti: 4 2 3 1 x 7 7 7 7 1 6 9 2 7 è monodimensionale. 7x1=7 e lo scrivo dopo il 7 del 77; poi, 7x3=21, scrivo l'1 del 21 e tengo il 2 in memoria; poi, 7x2=14, ma c'è il resto di 2, quindi diventa 16. Scrivo 6 e tengo in memoria l'1; poi, 7x4=28, ma c'è il resto di 1, quindi diventa 29. Scrivo 9 e cisto che è.

l'ultima operazione scrivo il 2 dopo. poi ricomincio. calcolo sul nastro comporta utilizzo di poche operazioni di base, 5:

1. HILBERT - GODEL - TURING 71. spostarsi a sinistra
2. spostarsi a destra
3. memorizzare ogni tanto qualche informazione
4. leggere
5. scrivere

in conclusione, ogni calcolo può essere inteso come un processo con le seguenti caratteristiche:

• viene eseguito scrivendo dei simboli nelle caselle di un nastro di carta
• a ogni passo la persona che esegue il calcolo fa attenzione al simbolo scritto in una sola di quelle caselle
• l'azione successiva dipenderà da questo simbolo e dallo stato mentale della personata
• la azione consisterà nello scrivere un simbolo nella casella osservata e eventualmente nello spostare l'attenzione sulla casella immediatamente a destra o sinistra.

Prendiamo adesso in considerazione una macchina di Turing con l'intento di sviluppare un linguaggio che, attraverso il suo alfabeto, sia in grado di descrivere esattamente le regole

Di trasformazione, cioè il passaggio da uno stato della macchina al successivo. Macchina a stati, passo sempre da uno stato precedente a uno successivo: la macchina è una configurazione che prima è di un certo tipo e poi sulla base del passaggio di stato cambia, ma sempre passo da uno stato a quello successivo.

Linguaggio macchina di Turing: HILBERT - GODEL - TURING. Uso di simboli che sono facili da capire ed è una macchina che accetta un numero e da come risultato un numero. Ogni singolo rettangolo consente di fare una trasformazione di stato:

• I sta per stato iniziale
• 0, 1, 2, 3... sta per simbolo che sto leggendo in quel momento
• quadrato dice di cancellare il numero che sto leggendo
• la freccia dice di spostarsi a destra di una casella
• P, D, F sta per finale
• asterisco dice basta

Il risultato dice se il numero è pari o dispari: 1 corrisponde a dispari e 0 corrisponde a pari. La macchina si ferma sempre, se le procedure non hanno fine allora non ci servono a nulla.

cambiare i simboli in 0 e 1. Ad esempio, possiamo rappresentare lo stato iniziale con 00, lo stato 1 con 01 e lo stato 2 con 10. In questo modo, possiamo riscrivere la macchina di Turing come segue: esercizio 1: stabilire cosa fa (la freccia in alto indica la posizione turing iniziale) IHILBERT - GODEL - TURING 9 I I Questa macchina continua all'infinito verso destra, non arriva ad un risultato. Non si blocca, continua ad elaborare all'infinito. esercizio 2: stabilire cosa fa questa macchina di turing nel seguente caso 1 2 1 (I) 1 (I) 2 Continua a sballottarsi a destra e sinistra all'infinito. Non sa cosa fare e non va avanti. e in questo caso 1 3 1 3 (I) La macchina trova uno stato che non sa leggere: il 3. Legge il primo, quando si sposta a destra e si trova il 3, non è compresa, non la capisce. Non fa nulla, problema della fermata. HILBERT - GODEL - TURING 10 Per farla diventare una macchina binaria basta leggerla guardando gli stati e si riesce a cambiare i simboli in 0 e 1.

trasformarla in una macchina di 0 e 1, allora è eseguibile da un computer: simboli I - P - D 0...9 - quadrato quadrato - 0 - 1 → - * P- D - F stati 3 11 3 2 3 bit 2 4 2 1 200 - 01 - 11 0000....-1111 00 - 01 - 11 0 - 1 00 - 01 - 11 in totale servirebbero 11 bit, per descrivere ciascuna regola di trasformazione in un linguaggio che capisce il computer, esempio la I potrebbe essere 00, P 01 e D 10, mentre per il secondo simbolo ho 4 bit, quindi lo zero sarà 0000, l'uno 0001, e via così fino al quadrato che sarà 1111. Stessa cosa per le altre colonne della tabella. per scrivere la trasfromazione D1quadrato→D con il sistema binaria sarà 10000100001 questi 1 e 0 sono tutti scritti su un nastro, perché Turing vuole che la sua macchina sia una macchina che scrive e legge le informazioni su un nastro monodimensionale. Il matematico inglese Alan Turing dimostrò nel 1936 che una tale macchina si poteva costruire e mostrò anche come costruirla. La

La struttura del nastro di questa nuova macchina è la seguente:

nastro vergine - stato attuale - simbolo attuale - dati - descrizione della macchina

Definiamo questa macchina una "macchina di turing universale", perché ha la particolarità di "imitare" tutte le altre macchine, compresa la nostra macchina per stabilire se un numero è pari o dispari. La macchina di Turing è una macchina che Turing ipotizza, astratta, facendo uso di nastro infinito, ma riportata a quella che è una macchina di Turing sottoforma di computer, il nastro non è più infinito (grande