Ieri era festa e tra una faccenda e l’altra ho saltato l’appuntamento con questa serie. Ho anche aggiunto qualche miglioramento agli articoli precedenti. Ma lasciando da parte questi inconvenienti, passiamo ad una nuova lezione.
Torniamo a parlare di passi di computazione di una MdT. Voglio scriverne una definizione per casi più formale:
Nel primo caso la funzione di transizione \(\delta\)
dice alla macchina di
lasciare in posizione la testina e di scrivere il carattere b che va a sostituire
il carattere a già presente.
Nel secondo stessa cosa, ma la funzione dice alla macchina di spostare a sinistra
la testina.
Il terzo e quarto caso sono simili: in entrambi i casi la testina dovrebbe
spostarsi a destra, con la differenza che nel caso 4 siamo già arrivati alla fine
della stringa. In tal caso viene esplicitato il fatto che il nastro contiene
almeno una cella vuota (sono infinite!) marcandola con \(\#\)
.
Convergenza di una computazione di una MdT
Definizione: una computazione \((q_0,w) \rightarrow^n(q',w')\)
converge o termina su \(w\)
se e soltanto se \(q' = h\)
. In questo caso usiamo la freccia in giù \(\downarrow\)
a seguito di una computazione per indicare che questa termina.
Definizione: una computazione, invece, diverge o non termina se e solo se \(\forall q', w'\text{ tali che }(q_0,w) \rightarrow^\star (q',w')\)
allora esiste \(q'',w'' \text{ tali che } (q',w') \rightarrow (q'',w'')\)
, cioè non viene mai raggiunto lo stato h di terminazione. In questo caso usiamo la freccia in su \(\uparrow\)
per indicare che una computazione diverge o non termina.
Inoltre possiamo indicare con \(M(w)\)
il fatto che la macchina M inizia
la sua computazione a partire dalla configurazione
\((q_0,\underline{\triangleright}w)\)
, cioè applichiamo M a w, un po'
come se M fosse una funzione.
Passiamo molto velocempente ad un altro formalismo che possiamo costruire a partire dalla definizione di algoritmo che avevamo dato all’inizio.
Prendiamo in esame un linguaggio WHILE, cioè un semplice linguaggio di programmazione iterativo semplicissimo, che opera solo su numeri naturali e booleani e che ha a disposizione soltanto un semplice ciclo while.
Saltando tutta la definizione del linguaggio mediante grammatiche BNF, arriviamo
subito al sodo. Un comando C calcola
\(f : Var \mapsto \mathbb{N} \iff \forall \sigma \in (Var \mapsto \mathbb{N}) : f(x) = n \iff \langle C, \sigma \rangle \rightarrow^\star \sigma' \wedge \sigma'(x) = n\)
.
Notiamo che σ è una funzione che associa variabili a numeri naturali e infatti σ è la funzione che descrive la memoria del calcolatore. Quel formalismo sopra lo possiamo leggere come “per ogni possibile memoria il comando C calcola la funzione f se e solo se l’esecuzione di C con la memoria σ porta ad una nuova memoria σ’ in cui la variabile x è associata ad n e f(x) = n”.
Così come esiste il concetto di Turing calcolabilità, esisto quello di WHILE calcolabilità che usa in pieno la definizione precedente. Una funzione f è WHILE calcolabile se esiste un comando C che la calcola.
A questo punto, abbiamo una definizione che funziona su numeri interi e verrebbe da chiedersi se questa non sia una limitazione. In realtà non lo è affatto, in quanto è possibile codificare qualsiasi tipo di dato in numero intero, applicarlo ad una MdT o un programma WHILE e infine decodificarlo nel dominio di partenza.
Domani vedremo un modo per codificare coppie di naturali in un singolo naturale.