BENVENUTO   |   Login   |   Registrati   |
Imposta Come Homepage   |   Ricerca Avanzata  CERCA  

ANNIVERSARI/ Interrogate il PC: vi risponderà come una macchina di Turing

Pubblicazione:

Foto: Fotolia  Foto: Fotolia
<< Prima pagina

Turing iniziò ad occuparsi del problema poco dopo la pubblicazione dei sorprendenti teoremi di incompletezza di Gödel. In essi, Gödel aveva dimostrato che all'interno di ogni sistema formale abbastanza potente da contenere l’aritmetica esistono proposizioni che il sistema non riesce a decidere, non riesce, cioè, a fornire una dimostrazione né di esse né della loro negazione. Inoltre, fra le proposizioni che tale sistema non riesce a dimostrare c'è anche quella che esprime la non-contraddittorietà (coerenza) del sistema.

Tali risultati rendevano improbabile l'esistenza di un algoritmo per Entscheidungsproblem. Turing concentrò, pertanto, il suo sforzo sulla ricerca di una dimostrazione di tale impossibilità e nel tentativo di fornire un modello adeguato del processo di calcolo arrivò a concepire quelle che da allora vengono chiamate le macchine di Turing. Una macchine di Turing manipola un insieme di dati contenuti nelle celle di un nastro di lunghezza infinita (in ogni fase della computazione, solo il contenuto di una porzione finita di tale nastro è significativo) sulla base di un insieme finito di regole prefissato.

La tesi di Turing-Church afferma che per ogni funzione calcolabile mediante un processo algoritmico, esiste una macchina di Turing che calcola tale funzione. A conferma di tale tesi, comunemente accettata, è stata dimostrata l'equivalenza di tutti i modelli di calcolo alternativi proposti in letteratura alla macchina di Turing. Sulla base di tale tesi, il problema originario può essere ridotto all'esistenza di una macchina di Turing in grado di risolverlo. Dalla prova della non esistenza di una tale macchina, segue l'indecidibilità dell'Entscheidungsproblem.

Sulla base di un'opportuna codifica numerica delle macchine di Turing e dei loro dati di input (codifiche analoghe erano state già utilizzate da Cantor e Gödel), Turing mostrò come il problema di stabilire se, data una macchina di Turing M e un insieme di dati di input I per essa, l'esecuzione di M su I termina o meno sia insolubile, ossia non esista un algoritmo (una macchina di Turing) in grado di risolverlo. La prova sfrutta il metodo della diagonale usato da Cantor per dimostrare che i numeri reali (infiniti) sono "piu" dei numeri naturali (anch'essi infiniti). Dato che il problema dell'arresto della macchina di Turing può essere espresso in logica del prim'ordine, la non esistenza di un algoritmo per l'Entscheidungsproblem segue immediatamente (se un tale algoritmo esistesse, potrebbe essere usato per risolvere il problema dell'arresto della macchine di Turing, che Turing ha mostrato essere indecidibile). Nei decenni successivi, tale tecnica di riduzione è stata impiegata con successo per dimostrare l'indecibilità di un grande numero di problemi algoritmici di natura assai diversa.

Una conferma definitiva della potenza della nozione di macchina di Turing venne dall'idea rivoluzionaria di una macchina di Turing universale. La tesi di Turing-Church afferma l'esistenza di una macchina di Turing per ogni funzione calcolabile. La macchina di Turing universale è una particolare macchina di Turing che riceve in input una descrizione di una qualsiasi (altra) macchina di Turing M e di un input I per essa e restituisce in output il risultato dell'elaborazione di I da parte di M. Turing provò l'esistenza di una tale macchina in modo costruttivo, ossia fornendo l'insieme di regole che la governano. Una delle novità radicali dell'idea di macchina universale è la rimozione della tradizionale distinzione tra macchine e dati. Fra i suoi dati di input, la macchina di Turing universale ha la descrizione di una (altra) macchina di Turing. Se i calcolatori così come noi li conosciamo sono assai diversi dalla macchina di Turing (la loro architettura si basa su un modello di calcolo alternativo equivalente proposto da von Neumann), dal punto di vista concettuale non c'è alcuna differenza: il calcolatore è una macchina di Turing universale.

 

 



< PAG. PREC.   PAG. SUCC. >