|
Tale teoria si occupa di capire se esistono o no algoritmi capaci di risolvere problemi.
Una funzione infatti è computabile se esiste un algoritmo che la calcola.
Si tratta quindi di procedimenti compiuti dalle cosiddette "Macchine di Turing."
La Macchina Universale di Turing, ha rivestito un ruolo molto importante nel campo dell'informatica nata subito dopo la Seconda Guerra Mondiale.
In altre parole si può dire che la teoria della computabilità alla cui nascita Turing diede un contributo cruciale, fu formulata nel contesto della fondazione della matematica attraverso strumenti logici.
Probabilmente Turing concepiva la macchina come a un modello della mente umana capace di emulare funzioni come: l'apprendimento, la capacità di sbagliare e correggere i propri errori, la scelta casuale.
La Macchina di Turing si ispira ai fondamenti matematici di Hilbert, il quale aveva sviluppato un programma per evitare il sorgere di possibili contraddizioni nell'ambito matematico.
Presentò dunque l'aritmetica elementare entro un sistema d'assiomi (enunciati che pur non essendo stati dimostrati, sono considerati veri).
•''Sono dell'opinione [...] che si può arrivare ad una fondazione del tutto rigorosa del concetto di numero, e precisamente mediante un metodo che io chiamo assiomatico [...] (Hilbert 1978)''
Tramite assiomi quindi, Hilbert cercò di dare alla matematica la possibilità di poggiare su basi stabili così da evitare il manifestarsi delle antinomie (due contraddizioni che possono essere entrambe dimostrate o giustificate es: tesi e antitesi)
La matematica quindi doveva essere formalizzata fino a diventare un "patrimonio di formule" dove ogni dimostrazione era un oggetto formale privo di contenuto.
A partire dagli anni '20 Hilbert comprese che per garantire affidabilità alla matematica non c'era bisogno della logica ma di una nuova disciplina, la Metamatematica o Teoria della Dimostrazione.
La Metamatematica, a differenza della matematica, permetteva il "ragionamento contenutistico" escluso nei sistemi formali per dimostrare la non-contradditorietà degli assiomi.
In un convegno tenutosi a KÖnisberg, Von Neumann, uno dei personaggi più importanti nell'informatica, dopo aver sostenuto la sua teoria secondo la quale: la patica matematica non poteva essere affrontata tramite questioni teoriche, rimase molto colpito dalle idee di Kurt GÖdel, logico ventiquattrenne, che presentò il suo risultato sull'incompletezza matematica.
Rifacendosi alle teorie di Hilbert circa la formalizzazione della matematica, GÖdel sostenne che era impossibile ottenere una dimostrazione di completezza e di non contradditrorietà da tali teorie.
Per rappresentare le proposizioni di un sistema formale adottò un metodo detto arimetizzazione- o GÖdelizzazione, in suo onore- che consisteva nell'attribuire un numero ad ogni segno che faceva parte del sistema, in modo da codificare mediante un numero naturale (il cosiddetto numero di GÖdel) ogni formula e dimostrazione del sistema.
Dopo i risultati di GÖdel, restava aperto una dei più importanti problemi posti da Hilbert nel 1928: il problema della decisone o Entscheidungsproblem, che consisteva nel determinare un metodo meccanico capace di stabilire se ogni affermazione matematica fosse vera o no, deciderne appunto la verità.
Nel 1931 questa ipotesi fu dimostrata irrealizzabile da GÖdel, negli stessi anni anche da Alonzo Church (suo allievo)e da Alan Turing.
Ma, per fissare matematicamente questa intuizione, era necessario dare una definizione di "metodo meccanico" e Turing occupandosi di ciò presentò quelle che, da allora in poi saranno note come le "Macchine di Turing."
Per risolvere il problema della decisione, Turing immaginò una macchina come un dispositivo di lettura e scrittura dotata di un numero finito di stati interni, di una memoria potenzialmente illimitata e di una tavola di istruzioni che doveva contenere le indicazioni di tutte le operazioni da svolgere in qualsiasi stato raggiunto dalla macchina.
La tavola era il vero cuore della macchina e gli stati interni vennero definiti come m-configurazioni indicati con q0, q1,...qn.
Quando veniva raggiunta la configurazione finale qn, il compito era considerato concluso e la macchina poteva fermarsi.
Venivano poi identificate le operazioni da eseguire, spostamento a destra e a sinistra nella memoria, scrittura o cancellazione di un simbolo e alla fine si trovava l'indicazione del nuovo stato interno al quale la macchina doveva accedere dopo aver effettuato l'operazione.
Turing ebbe un'intuizione geniale: il nastro della macchina poteva essere usato per riportare numeri scritti cifra per cifra oppure per trascrivere istruzioni scritte carattere per carattere.
Pensò di avere una macchina universale la quale, tramite il description number era in grado di compiere qualsiasi operazione eseguibile da un'altra macchina.
Turing cercò di mostrare la capacità della macchina universale di "emulare" l'attività umana del calcolatore, cioè di agire "come se" fosse l'uomo ad eseguire il compito.
Cercò quindi con una serie di limiti "finitisti" di rendere la macchina compatibile con la capacità umana nell'eseguire calcoli.
===L’insolubilità dell’''Entscheidungsproblem''===
| 