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:

$$ \begin{align} 1) & (q, u\underline{a}v) \rightarrow (q',u\underline{b}v) & \text{se }\delta(q,a)=(q',b,―) \\ 2) & (q, uc\underline{a}v) \rightarrow (q', u\underline{c}bv) & \text{se }\delta(q,a)=(q',b,L) \\ 3) & (q,u\underline{a}cv) \rightarrow (q', ub\underline{c}v) & \text{se }\delta(q,a)=(q',b,R) \\ 4) & (q,u\underline{a}) \rightarrow (q',ub\underline{\#}) & \text{se }\delta(q,a)=(q',b,R) \end{align} $$

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 \(\#\) .


Passiamo ora alla definizione di convergenza di una computazione di una MdT.

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.

Una computazione, invece, diverge o non termina se e solo se \(\forall q',w'\text{ tali che }(q_0,w) \rightarrow^\star (q',w') \Rightarrow \exists q'',w'' \text{ tali che } (q',w') \rightarrow (q'',w'')\) . 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{▷}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} \Leftrightarrow \forall \sigma \in (Var \mapsto \mathbb{N}) : f(x) = n \Leftrightarrow \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.