Macchina di Turing: differenze tra le versioni

Versione delle 13:03, 19 set 2025

Versione delle 11:39, 21 ott 2025

Riga 44:

La macchina può agire sopra un nastro che si presenta come una sequenza di caselle nelle quali possono essere registrati simboli di un ben determinato alfabeto finito; essa è dotata di una testina di lettura e scrittura (I/O) con cui è in grado di effettuare operazioni di lettura e scrittura su una casella del nastro. La macchina si evolve nel tempo, e ad ogni istante si può trovare in uno [[stato interno]] ben determinato, facente parte di un [[insieme finito]] di stati. Inizialmente sul nastro viene posta una stringa che rappresenta i dati che caratterizzano il problema che viene sottoposto alla macchina. La macchina è dotata anche di un repertorio finito di istruzioni che determinano la sua evoluzione in conseguenza dei dati iniziali. L'evoluzione si sviluppa per passi successivi che corrispondono a una sequenza discreta di istanti successivi. Le proprietà precedenti sono comuni a molte macchine formali ([[automa a stati finiti]], [[automa a pila]], ...). Caratteristica delle MdT è quella di disporre di un nastro potenzialmente infinito, cioè estendibile quanto si vuole qualora questo si renda necessario.

Ogni passo dell'evoluzione viene determinato dallo stato attuale <math>s</math> nel quale la macchina si trova, e dal carattere <math>c</math> che la testina di I/O trova sulla casella del nastro su cui è posizionata, e si concretizza nell'eventuale modifica del contenuto della casella, nell'eventuale spostamento della testina di una posizione verso destra o verso sinistra, e nell'eventuale cambiamento dello stato. Quali azioni vengono effettuate a ogni passo viene determinato dall'istruzione, che supponiamo unica, che ha come prime due componenti <math>s</math> e <math>c</math>; le altre tre componenti dell'istruzione forniscono nell'ordine il nuovo stato, il nuovo carattere, e una richiesta di spostamento verso sinistrasopra, nullo, o verso destrasotto.

Un'evoluzione potenziamento della macchina consiste in una sequenza di possibili "configurazioni", ognuna di queste costituita dallo stato interno attuale, dal contenuto del nastro (una stringa di lunghezza finita), e dalla posizione sul nastro della testina di I/O. Nei casi più semplici l'evoluzione ad un certo punto si arresta, in quanto non si trova nessuna istruzione in grado di farla eccitare e quindi di proseguire. Si può avere un arresto in una configurazione "utile", dal punto di vista del problema che si vuole risolvere; in tal caso quello che si trova registrato sul nastro all'atto dell'arresto, rappresenta il risultato dell'elaborazione. Si può avere però anche un arresto "inutile", che va considerato come una conclusione erronea dell'elaborazione. Va subito detto che può anche accadere che un'evoluzione non abbia mai fine (Vedi la successiva sezione e [[Problema della fermata]]).

==== Impostazione formale ====