 |
 |
|
|
Le macchine di Turing sono strumenti potenti: non si limitano a trovare la soluzione di semplici problemi di aritmetica, come l'addizione, ma permettono di computare un ambito estremamente ampio di funzioni matematiche: in effetti, per quanto ne sappiamo, tutte le funzioni computabili attraverso un metodo definito e un numero finito (anche se magari enormemente grande) di passi. Naturalmente, le macchine di Turing capaci di computare funzioni particolarmente complicate lavoreranno a loro volta su lunghi insiemi di regole, e arriveranno alla soluzione svolgendo un gran numero di passi.
Ma veramente le macchine di Turing sono in grado di computare tutte le funzioni computabili? E' difficile dare con sicurezza una risposta affermativa a questo interrogativo: può ben darsi che un giorno qualcuno scopra dei metodi effettivi di computazione in grado di computare funzioni che una normale macchina di Turing non è in grado di affrontare. Tuttavia, per ora non abbiamo trovato metodi simili: fino ad ora ogni funzione computabile attraverso metodi che da un punto di vista intuitivo possiamo considerare effettivi risulta anche computabile da una opportuna macchina di Turing. Questa situazione è rispecchiata da una formulazione della cosiddetta tesi di Church (dal nome del matematico e logico Alonzo Church), secondo la quale l'insieme di funzioni computabili utilizzando una macchina di Turing coincide con l'insieme delle funzioni effettivamente computabili.
Non sappiamo se la tesi di Church sia corretta (e probabilmente non lo sapremo mai – anche se un giorno potremmo accorgerci che è sbagliata). In compenso, possiamo dimostrare che esistono alcune funzioni che una macchina di Turing non è in grado di computare. Tuttavia, si tratta di funzioni che non sappiamo computare neanche in altri modi.
Non c'è niente di scandaloso nel fatto che alcune funzioni non siano computabili. Un caso di funzione non computabile è la funzione corrispondente al problema della fermata. Per capire di che si tratta, cominciamo dal ricordare che vi sono funzioni parziali, funzioni, cioè, tali che per alcuni argomenti non esiste (non è definito) alcun valore. Così, ad esempio, la funzione "l'attuale presidente della Repubblica del paese 'x'" ha un valore se sostituiamo a 'x' uno stato repubblicano (come l'Italia), ma non ha un valore se sostituiamo a 'x' una monarchia (come l'Inghilterra). Quando abbiamo una macchina di Turing che riceve come input valori per i quali la corrispondente funzione non è definita, la macchina di Turing non si ferma. Il vero guaio è che, messi davanti a una macchina di Turing (cioè a una particolare configurazione iniziale del nastro e all'insieme di regole che determinano il funzionamento di quella particolare macchina), possiamo non essere in grado di dire se quella macchina si fermerà o no. E non solo non sappiamo farlo noi, ma non lo saprebbe fare neppure una ipotetica 'macchina di Turing di secondo livello' alla quale fornissimo come input una rappresentazione adeguata dello stato iniziale e delle regole di funzionamento della macchina di Turing di primo livello che stiamo esaminando. In sostanza, il problema della fermata (trovare una procedura effettiva che permetta di stabilire, per ogni macchina di Turing data, se quella macchina di Turing si fermerà o no) non è risolvibile, o quantomeno non lo è attraverso una macchina di Turing. In altre parole, una corrispondente funzione che abbia un certo valore (per esempio 1) se la macchina considerata si ferma per l'input in questione e un altro valore (per esempio 0) se invece non si ferma, non è una funzione Turing-computabile.
Le tematiche discusse in questa scheda sono evidentemente complesse e piuttosto astratte, e non possiamo pretendere di averle affrontate se non in maniera parziale, generica e sommaria; chi fosse interessato a una trattazione più approfondita può consultare (meglio se con l'aiuto del professore) un buon manuale di logica che si occupi di teoria della computabilità. Un classico in materia è il libro Computability and Logic di George Boolos e Richard Jeffrey, Cambridge University Press, 3a edizione, 1989.