Filosofia dell'informazione/Computazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 28:
== Cos'è una macchina di Turing?==
''Una macchina di Turing'' (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. In altre parole, è un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro potenzialmente infinito su cui può leggere e scrivere dei simboli.
''
La macchina di Turing'' consiste in una memoria senza limiti e uno scanner che si muove avanti e indietro nella memoria, simbolo per simbolo, leggendo ciò che trova e scrivendo ulteriori simboli.
La memoria consiste in un nastro diviso in quadrati. Ciascuna casella può essere vuota o può contenere un singolo simbolo, "0" o "1", ad esempio, o qualche altro simbolo preso da un alfabeto infinito. Lo scanner è in grado di esaminare solo un quadrato di nastro alla volta (il "quadrato scansionato"). Il nastro è il supporto di memorizzazione generico della macchina, che funge da veicolo per l'input e l'output e come memoria di lavoro per memorizzare i risultati dei passaggi intermedi del calcolo.
Il nastro può contenere anche un programma di istruzioni. L'input che è inscritto sul nastro prima dell'inizio del calcolo deve essere composto da un numero finito di simboli. Tuttavia, il nastro stesso ha una lunghezza illimitata - dal momento che l'obiettivo di Turing era quello di mostrare che ci sono compiti che queste macchine non sono in grado di eseguire, anche con memoria di lavoro illimitata e tempo illimitato.
| |||