Le Macchine di Turing non vedono se vi sarà o meno un arresto nel processo di calcolo di un algoritmo. Mi dimostrereste come questo avviene? Esiste una MdT che scelga una struttura algoritmica appropriata per risolvere un problema nuovo che le venga presentato? Complimenti e grazie

Alan Turing nel 1936 propose la macchina di Turing (mdT) come modello di
calcolo per definire il concetto di problema calcolabile, ovvero risolvibile con un
computer, molto prima della costruzione dei computer moderni.
Turing ebbe questa idea dall’osservazione di un soggetto che deve eseguire
calcoli su un foglio di carta divisa in quadretti, in cui in ogni istante il
comportamento del calcolatore è determinato dai simboli che osserva e dallo
stato della sua mente. L’attenzione di Turing era rivolta al processo di
calcolo indipendentemente dalla sua realizzazione fisica.

La mdT funziona su intervalli discreti di tempo; ad ogni istante il suo
stato dipende da quello precedente. La sua struttura è formata da una
testina che può scrivere e leggere simboli e da un nastro di lunghezza infinita
diviso in caselle; in ogni casella può essere scritto un solo simbolo scelto
in un alfabeto di simboli.

La mdT che comanda la testina è definita in ogni
istante con una quintupla di elementi (s,i,S(s,i),I(s,i),V(s,i)) in cui:

  • s è lo stato all’istante precedente.
  • i è il simbolo letto all’istante presente.
  • S(s,i) è lo stato all’istante successivo in funzione dei due parametri.
  • I(s,i) è il simbolo scritto dalla macchina all’istante successivo in
    funzione dei due parametri.
  • V(s,i) è il movimento destra/sinistra in funzione dei due parametri.

Questa struttura elementare può eseguire tutti i calcoli eseguibili da un
computer attuale, anche se richiede molto più tempo.

Lo stato iniziale della mdT contiene la rappresentazione simbolica
dell’espressione da calcolare e dei movimenti da eseguire; i simboli che restano
sul nastro rappresentano il risultato.
Un algoritmo viene rappresentato considerando gli stati iniziali e finali e
la sequenza degli spostamenti che deve fare la testina. In questo modo il
concetto di algoritmo diventa simile a quello di mdT; si può affermare che
un problema è calcolabile se esiste un algoritmo che lo risolve, cioè se
esiste una mdT che lo risolve.

Esistono però problemi per i quali non esiste nessuna mdT che li risolve:
sono i problemi non calcolabili. Turing dimostrò che non è risolubile il
problema dell’arresto: non è possibile costruire una mdT che può decidere se
un’altra mdT si arresterà o no secondo uno stato iniziale ed una
rappresentazione simbolica sul nastro. Allo stesso modo, dato un generico
programma ed i suoi dati in ingresso, non è possibile decidere se la
macchina che lo esegue si fermerà o no senza far girare il programma, ma
solo con l’analisi del programma e dell’input opportunamente codificati. Si
può dimostrare, tramite la tesi di Church1,
che un problema non calcolabile
secondo la mdT non è calcolabile nemmeno con altri modelli di calcolo diversi
dalla mdT.

Turing usò la tecnica della dimostrazione per assurdo. Supponiamo che questa
mdT esista; avrà come dati in ingresso una descrizione di una qualsiasi mdT
e in uscita dirà si o no, a seconda se si ferma o non si ferma
nell’esecuzione del calcolo. Se questa macchina esiste deve funzionare per
qualsiasi mdT. Ad un certo punto avrà in ingresso la propria
descrizione e
dovrà dare una risposta su se stessa. Quindi dovrebbe sapere se è in grado
di fermarsi prima di essersi fermata e dare risposta sulla propria fermata
mentre è in funzione, ma questo è un assurdo nato dall’aver supposto
l’esistenza della mdT, per cui essa non esiste.
Quindi, in un certo senso, le
macchine non possono analizzare sé stesse.

Una mdT potrebbe avere una famiglia di strutture algoritmiche e poi dovrebbe
decidere se, usando una certa struttura, il calcolo si arresterà o no, cioè
se quella struttura risolve il problema. Ma, per come è definita la mdT e
per quanto dimostrato prima, tale mdT non può esistere.
Nei testi seguenti si trovano dimostrazioni e definizioni più formali.

  1. Sangalli Arturo, L’importanza di essere fuzzy: matematica e computer,
    Bollati Boringhieri.
  2. Harel David, Computer a responsabilità limitata : dove le macchine non
    riescono ad arrivare
    , Einaudi.


Nota 1: Vedere anche la risposta:

http://www.vialattea.net/esperti/php/risposta.php?numero=8444