Macchina di Turing che inverte una sequenza binaria

Stato iniziale : la testina di lettura e scrittura è posizionata a sinistra del bit più significativo

Stato finale : la testina di lettura e scrittura è posizionata sul blank che precedeil bit più significativo

Descrizione algoritmo :

a) Si effettua una specchiatura del n° binario con asse di rotazione intorno al bit più significativo e sostituzione dei bit copiati con altrettanti *.

b) Si sostituisce la cifra che precede il 1° * con un altro * e la si va a trascrivere al posto della ultimo *

c) Si ritorna al 1° * , se è un n° si torna al passo b mentre se è un blank si cancellano tutti gli * a destra sin quando non si raggiunge un bit e si termina.

Matrice funzionale

	b	0	1	*	descrizione
qo		* q2 sx	* q1 sx		stato iniziale
q1	1 q3 dx	0 q1 sx	1 q1 sx		Sostituisco con 1 il 1° blank che incontro andando a sinistra
q2	0 q3 dx	0 q2 sx	1 q2 sx		Sostituisco con 0 il 1° blank che incontro andando a sinistra
q3		0 q3 dx	1 q3 dx	* q4 dx	Cerco il primo * a destra
q4	b q5 dx	* q2 sx	* q1 sx	* q4 dx	Cerco l´ultimo * a destra
q5	b q10dx	* q8 dx	* q6 dx	* q5 sx	Sostituisco con * la 1ª cifra a sinistra degli * se essa è un blank allora esco dal ciclo
q6	b q7 sx	0 q7 sx	1 q7 sx	* q6 dx	Cerco l´ultimo * a destra per sostituirlo con 1
q7				1 q5 sx	Sostituisco con 1 l´ultimo * a destra
q8	b q9 sx	0 q9 sx	1 q9 sx	* q8 dx	Cerco l´ultimo * a destra per sostituirlo con 0
q9				0 q5 sx	Sostituisco con 0 l´ultimo * a destra
q10		0 q11 sx	1 q11 sx	b q10dx	Sostituisco tutti gli * con blank
q11					Fine

Esempio di computazione della stringa

q10

q11