Domanda 8 delle tracce

Impara a programmare una macchina di Turing

Parti dall'idea, scegli gli stati e scrivi le transizioni. Segui l'esempio guidato, poi prova la tua macchina nel simulatore o esplora le soluzioni delle tracce.

Nastro, testina e stati

\delta

Come leggere una transizione

M=(K,\Sigma,\delta,s)

Dall’idea alla tabella: quattro passi

Descrivi l'idea. Scrivi in due righe cosa farai, prima di scegliere gli stati. Assegna gli stati. Uno per ogni informazione da ricordare: un bit, un riporto, una fase del calcolo. Copri i casi limite. Controlla input vuoto, overflow e arrivo all'inizio del nastro. Simula un esempio. Usa un input piccolo e controlla ogni transizione. Per leggere le simulazioni, guarda la cella tra parentesi quadre: è quella sotto la testina. Ogni riga mostra un passo. Puoi poi verificare la tua macchina sui casi di prova del laboratorio.

Il blocco da riusare: raggiungere l’ultima cifra

p

$p$	$\sigma$	$\delta(p, \sigma)$
$s$	$\triangleright$	$(s, \triangleright, \rightarrow)$
$s$	$b$	$(s, b, \rightarrow)$
$s$	$\sqcup$	$(q, \sqcup, \leftarrow)$ : da qui cambia da macchina a macchina

Esempio guidato: l'incremento di 1

Costruisci la tabella in quattro passi. Le righe aggiunte a ogni passo sono evidenziate; alla fine puoi eseguire la macchina.

Aggiungere 1 a un numero binario. Parti da destra: trasforma ogni 1 finale in 0, poi cambia il primo 0 in 1. Per raggiungere l'ultima cifra, la macchina scorre l'input fino alla prima cella vuota e torna indietro di una posizione. Queste prime tre righe fanno proprio questo.

Transizioni scritte finora

δ(s, ▷) = (s, ▷, →)supera l'inizio del nastro
δ(s, b) = (s, b, →)vai in fondo
δ(s, ⊔) = (q, ⊔, ←)fine input, inizia il riporto

Come scrivere le transizioni

\delta(q, 1) = (q, 0, \leftarrow)

Prova tu

Scegli un esercizio e completa le transizioni. Usa «Verifica i casi di prova» per confrontare i risultati con quelli attesi. Il programma si salva automaticamente in questo browser.

Scegli un esercizio

Nastro

▷1011⊔⊔⊔

Stato sPasso 0

Soluzioni delle tracce

Apri un esercizio per leggere il ragionamento, consultare la tabella ed eseguire la soluzione.

Incremento di 1funzione · 1 nastro

Nelle tracce: F14

111 + 1 = 1000

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\sqcup$	$(q, \sqcup, \leftarrow)$	fine input, inizia il riporto
$q$	$1$	$(q, 0, \leftarrow)$	$1 + \text{riporto} = 0$ , il riporto continua
$q$	$0$	$(h, 1, -)$	riporto assorbito, fine
$q$	$\triangleright$	$(o, \triangleright, \rightarrow)$	overflow
$o$	$0$	$(o', 1, \rightarrow)$	la prima cifra diventa 1
$o'$	$0$	$(o', 0, \rightarrow)$	scorre le altre cifre
$o'$	$\sqcup$	$(h, 0, -)$	aggiunge lo 0 in coda

\delta(s, \triangleright) = (s, \triangleright, \rightarrow)

Prova la soluzione

Nastro

▷1011⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ -> s ▷ R      # supera l'inizio del nastro
s b -> s b R      # vai in fondo
s ⊔ -> q ⊔ L      # fine input, inizia il riporto
q 1 -> q 0 L      # 1 + riporto = 0, il riporto continua
q 0 -> h 1 S      # riporto assorbito, fine
q ▷ -> o ▷ R      # overflow
o 0 -> o' 1 R     # la prima cifra diventa 1
o' 0 -> o' 0 R    # scorre le altre cifre
o' ⊔ -> h 0 S     # aggiunge lo 0 in coda

Moltiplicazione per 2funzione · 1 nastro

Nelle tracce: F13

h

$p$	$\sigma$	$\delta(p, \sigma)$
$s$	$\sqcup$	$(h, 0, -)$

\delta(s, \triangleright) = (s, \triangleright, \rightarrow)

Prova la soluzione

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ -> s ▷ R      # supera l'inizio del nastro
s b -> s b R      # vai in fondo
s ⊔ -> h 0 S      # fine input: scrive 0 e si ferma

Moltiplicazione per 4funzione · 1 nastro

Nelle tracce: G20v2

101 \to 10100

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\triangleright$	$(s, \triangleright, \rightarrow)$	supera l'inizio del nastro
$s$	$b$	$(s, b, \rightarrow)$	scorre l'input fino in fondo
$s$	$\sqcup$	$(q, 0, \rightarrow)$	fine input: scrive il primo 0
$q$	$\sqcup$	$(h, 0, -)$	scrive il secondo 0 e si ferma

Prova la soluzione

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ -> s ▷ R      # supera l'inizio del nastro
s b -> s b R      # vai in fondo
s ⊔ -> q 0 R      # fine input: scrive il primo 0
q ⊔ -> h 0 S      # scrive il secondo 0 e si ferma

Divisione intera per 2funzione · 1 nastro

Nelle tracce: F05, F07

101 \to 10

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\sqcup$	$(q, \sqcup, \leftarrow)$	fine input
$q$	$b$	$(r, \sqcup, \leftarrow)$	cancella l'ultima cifra
$r$	$b$	$(h, b, -)$	è rimasta almeno una cifra
$r$	$\triangleright$	$(z, \triangleright, \rightarrow)$	non è rimasto niente…
$z$	$\sqcup$	$(h, 0, -)$	…quindi scrive 0

\delta(s, \triangleright) = (s, \triangleright, \rightarrow)

Prova la soluzione

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ -> s ▷ R      # supera l'inizio del nastro
s b -> s b R      # vai in fondo
s ⊔ -> q ⊔ L      # fine input
q b -> r ⊔ L      # cancella l'ultima cifra
r b -> h b S      # è rimasta almeno una cifra
r ▷ -> z ▷ R      # non è rimasto niente…
z ⊔ -> h 0 S      # …quindi scrive 0

Divisione intera per 4funzione · 1 nastro

Nelle tracce: G20v5

10110 \to 101

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\triangleright$	$(s, \triangleright, \rightarrow)$	supera l'inizio del nastro
$s$	$b$	$(s, b, \rightarrow)$	scorre l'input fino in fondo
$s$	$\sqcup$	$(q, \sqcup, \leftarrow)$	fine input, torna sull'ultima cifra
$q$	$b$	$(r, \sqcup, \leftarrow)$	cancella l'ultima cifra
$r$	$b$	$(t, \sqcup, \leftarrow)$	cancella la penultima cifra
$r$	$\triangleright$	$(z, \triangleright, \rightarrow)$	l'input aveva una sola cifra
$t$	$b$	$(h, b, -)$	è rimasta almeno una cifra: fine
$t$	$\triangleright$	$(z, \triangleright, \rightarrow)$	non è rimasto niente…
$z$	$\sqcup$	$(h, 0, -)$	…quindi scrive 0

Prova la soluzione

Nastro

▷10110⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ -> s ▷ R      # supera l'inizio del nastro
s b -> s b R      # vai in fondo
s ⊔ -> q ⊔ L      # fine input, torna sull'ultima cifra
q b -> r ⊔ L      # cancella l'ultima cifra
r b -> t ⊔ L      # cancella la penultima cifra
r ▷ -> z ▷ R      # l'input aveva una sola cifra
t b -> h b S      # è rimasta almeno una cifra: fine
t ▷ -> z ▷ R      # non è rimasto niente…
z ⊔ -> h 0 S      # …quindi scrive 0

Resto della divisione per 2funzione · 1 nastro

Nelle tracce: F02, F04, F06, G20v1

c_0

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\sqcup$	$(q, \sqcup, \leftarrow)$	fine input
$q$	$0$	$(c_0, \sqcup, \leftarrow)$	ricorda 0
$q$	$1$	$(c_1, \sqcup, \leftarrow)$	ricorda 1
$c_i$	$b$	$(c_i, \sqcup, \leftarrow)$	cancella le altre cifre
$c_i$	$\triangleright$	$(w_i, \triangleright, \rightarrow)$	inizio del nastro
$w_i$	$\sqcup$	$(h, i, -)$	scrive il resto

\delta(s, \triangleright) = (s, \triangleright, \rightarrow)

Prova la soluzione

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ -> s ▷ R      # supera l'inizio del nastro
s b -> s b R      # vai in fondo
s ⊔ -> q ⊔ L      # fine input
q 0 -> c0 ⊔ L     # ricorda 0
q 1 -> c1 ⊔ L     # ricorda 1
c0 b -> c0 ⊔ L    # cancella le altre cifre
c1 b -> c1 ⊔ L
c0 ▷ -> w0 ▷ R    # inizio del nastro
c1 ▷ -> w1 ▷ R
w0 ⊔ -> h 0 S     # scrive il resto
w1 ⊔ -> h 1 S

Calcolare −x in complemento a duefunzione · 1 nastro

Nelle tracce: L18

-x

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\sqcup$	$(c, \sqcup, \leftarrow)$	fine input
$c$	$0$	$(c, 0, \leftarrow)$	copia gli 0 finali
$c$	$1$	$(i, 1, \leftarrow)$	copia il primo 1, poi inverte
$c$	$\triangleright$	$(h, \triangleright, \rightarrow)$	$x = 0$ , quindi $-x = 0$
$i$	$0$	$(i, 1, \leftarrow)$	inverte
$i$	$1$	$(i, 0, \leftarrow)$	inverte
$i$	$\triangleright$	$(h, \triangleright, \rightarrow)$	fine

\delta(s, \triangleright) = (s, \triangleright, \rightarrow)

Prova la soluzione

Nastro

▷0110⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ -> s ▷ R      # supera l'inizio del nastro
s b -> s b R      # vai in fondo
s ⊔ -> c ⊔ L      # fine input
c 0 -> c 0 L      # copia gli 0 finali
c 1 -> i 1 L      # copia il primo 1, poi inverte
c ▷ -> h ▷ R      # x = 0, quindi −x = 0
i 0 -> i 1 L      # inverte
i 1 -> i 0 L
i ▷ -> h ▷ R      # fine

Interi positivi dispari in complemento a duedecisione · 1 nastro

Nelle tracce: F01

p

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\triangleright$	$(s, \triangleright, \rightarrow)$
$s$	$0$	$(a, 0, \rightarrow)$	segno positivo
$s$	$1$	$(\text{no}, 1, -)$	negativo
$s$	$\sqcup$	$(\text{no}, \sqcup, -)$	stringa vuota
$a$	$b$	$(a, b, \rightarrow)$	va in fondo
$a$	$\sqcup$	$(t, \sqcup, \leftarrow)$	torna sull'ultimo bit
$t$	$1$	$(\text{yes}, 1, -)$	dispari
$t$	$0$	$(\text{no}, 0, -)$	pari (o zero)

Prova la soluzione

Nastro

▷011⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ -> s ▷ R
s 0 -> a 0 R      # segno positivo
s 1 -> no 1 S     # negativo
s ⊔ -> no ⊔ S     # stringa vuota
a b -> a b R      # va in fondo
a ⊔ -> t ⊔ L      # torna sull'ultimo bit
t 1 -> yes 1 S    # dispari
t 0 -> no 0 S     # pari (o zero)

Stringhe non palindrome: macchina nondeterministicadecisione · 2 nastri · nondeterministica

Nelle tracce: G20v4, FE23, MA23

x_i \neq x_{n+1-i}

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$a$	$\sqcup$	$s$	$a, \rightarrow$	$I, \rightarrow$	scelta 1: salta la cifra $a$
$s$	$a$	$\sqcup$	$g_a$	$a, \rightarrow$	$\sqcup, -$	scelta 2: confronta $a$ (ricordata nello stato)
$s$	$\sqcup$	$\sqcup$	$\text{no}$	$\sqcup, -$	$\sqcup, -$	nessuna cifra scelta
$g_a$	$b$	$\sqcup$	$g_a$	$b, \rightarrow$	$\sqcup, -$	va in fondo
$g_a$	$\sqcup$	$\sqcup$	$c_a$	$\sqcup, \leftarrow$	$\sqcup, \leftarrow$	torna indietro su entrambi
$c_a$	$b$	$I$	$c_a$	$b, \leftarrow$	$I, \leftarrow$	consuma una tacca per passo
$c_a$	$b \neq a$	$\triangleright$	$\text{yes}$	$b, -$	$\triangleright, \rightarrow$	cifre simmetriche diverse
$c_a$	$b = a$	$\triangleright$	$\text{no}$	$b, -$	$\triangleright, \rightarrow$	questo ramo rigetta

Prova la soluzione

Nastro 1

▷100⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ ▷ -> s ▷ R ▷ R
s 0 ⊔ -> s 0 R I R      # scelta 1: salta la cifra 0
s 0 ⊔ -> g0 0 R ⊔ S     # scelta 2: confronta la cifra 0
s 1 ⊔ -> s 1 R I R      # scelta 1: salta la cifra 1
s 1 ⊔ -> g1 1 R ⊔ S     # scelta 2: confronta la cifra 1
s ⊔ ⊔ -> no ⊔ S ⊔ S     # nessuna cifra scelta
g0 b ⊔ -> g0 b R ⊔ S    # va in fondo
g1 b ⊔ -> g1 b R ⊔ S
g0 ⊔ ⊔ -> c0 ⊔ L ⊔ L    # torna indietro su entrambi
g1 ⊔ ⊔ -> c1 ⊔ L ⊔ L
c0 b I -> c0 b L I L    # consuma una tacca per passo
c1 b I -> c1 b L I L
c0 1 ▷ -> yes 1 S ▷ R   # cifre simmetriche diverse
c1 0 ▷ -> yes 0 S ▷ R
c0 0 ▷ -> no 0 S ▷ R    # questo ramo rigetta
c1 1 ▷ -> no 1 S ▷ R

Palindrome: macchina nondeterministica a 2 nastridecisione · 2 nastri · nondeterministica

Nelle tracce: F03

\sqcup

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$b$	$\sqcup$	$s$	$b, \rightarrow$	$b, \rightarrow$	scelta 1: copia $b$ , la prima metà continua
$s$	$b$	$\sqcup$	$m$	$b, \rightarrow$	$\sqcup, \leftarrow$	scelta 2: $b$ è il centro (lunghezza dispari), lo salta
$s$	$b$	$\sqcup$	$m$	$b, -$	$\sqcup, \leftarrow$	scelta 3: la prima metà finisce prima di $b$ (lunghezza pari)
$s$	$\sqcup$	$\sqcup$	$m$	$\sqcup, -$	$\sqcup, \leftarrow$	fine dell'input senza scelte: accetta solo la stringa vuota
$m$	$b$	$b$	$m$	$b, \rightarrow$	$b, \leftarrow$	cifre simmetriche uguali
$m$	$\sqcup$	$\triangleright$	$\text{yes}$	$\sqcup, -$	$\triangleright, \rightarrow$	finite insieme: palindroma

Prova la soluzione

Nastro 1

▷101⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ ▷ -> s ▷ R ▷ R
s b ⊔ -> s b R b R      # scelta 1: copia b, la prima metà continua
s b ⊔ -> m b R ⊔ L      # scelta 2: b è il centro (lunghezza dispari), lo salta
s b ⊔ -> m b S ⊔ L      # scelta 3: la prima metà finisce prima di b (lunghezza pari)
s ⊔ ⊔ -> m ⊔ S ⊔ L      # fine dell'input senza scelte
m b b -> m b R b L      # cifre simmetriche uguali
m ⊔ ▷ -> yes ⊔ S ▷ R    # finite insieme: palindroma

Palindrome: macchina deterministica a 2 nastridecisione · 2 nastri

Nelle tracce: F12, G17

s

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$b$	$\sqcup$	$s$	$b, \rightarrow$	$b, \rightarrow$	copia l'input
$s$	$\sqcup$	$\sqcup$	$r$	$\sqcup, \leftarrow$	$\sqcup, -$	fine dell'input: la testina 2 resta dopo la copia
$r$	$b$	$\sqcup$	$r$	$b, \leftarrow$	$\sqcup, -$	riavvolge il 1° nastro
$r$	$\triangleright$	$\sqcup$	$c$	$\triangleright, \rightarrow$	$\sqcup, \leftarrow$	testina 1 sulla prima cifra, testina 2 sull'ultima
$c$	$b$	$b$	$c$	$b, \rightarrow$	$b, \leftarrow$	cifre simmetriche uguali
$c$	$b$	$\bar b$	$\text{no}$	$b, -$	$\bar b, -$	cifre simmetriche diverse
$c$	$\sqcup$	$\triangleright$	$\text{yes}$	$\sqcup, -$	$\triangleright, \rightarrow$	finite insieme: palindroma

Prova la soluzione

Nastro 1

▷010⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ ▷ -> s ▷ R ▷ R
s b ⊔ -> s b R b R      # copia l'input
s ⊔ ⊔ -> r ⊔ L ⊔ S      # fine dell'input: la testina 2 resta dopo la copia
r b ⊔ -> r b L ⊔ S      # riavvolge il 1° nastro
r ▷ ⊔ -> c ▷ R ⊔ L      # testina 1 sulla prima cifra, testina 2 sull'ultima
c b b -> c b R b L      # cifre simmetriche uguali
c b b̄ -> no b S b̄ S     # cifre simmetriche diverse
c ⊔ ▷ -> yes ⊔ S ▷ R    # finite insieme: palindroma

Confronto tra numeri binari: x ≤ ydecisione · 2 nastri

Nelle tracce: G20v3, MZ22, GE23

x \le y

Stato	letto₁ ( $y$ )	letto₂ ( $x$ )	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$b$	$\sqcup$	$s$	$b, \rightarrow$	$b, \rightarrow$	copia $x$
$s$	$;$	$\sqcup$	$r$	$;, \rightarrow$	$\sqcup, \leftarrow$	testina 1 sulla prima cifra di $y$
$r$	$\sigma$	$b$	$r$	$\sigma, -$	$b, \leftarrow$	riavvolge il 2° nastro
$r$	$\sigma$	$\triangleright$	$e$	$\sigma, -$	$\triangleright, \rightarrow$	pronto a confrontare
$e$	$b$	$b$	$e$	$b, \rightarrow$	$b, \rightarrow$	cifre uguali
$e$	$1$	$0$	$l$	$1, \rightarrow$	$0, \rightarrow$	$x$ minore di $y$
$e$	$0$	$1$	$\text{no}$	$0, -$	$1, -$	$x$ maggiore di $y$
$l$	$b$	$b'$	$l$	$b, \rightarrow$	$b', \rightarrow$	ormai conta solo la lunghezza ( $b'$ è un altro bit qualsiasi)
$e$ o $l$	$\sqcup$	$\sqcup$	$\text{yes}$	$\sqcup, -$	$\sqcup, -$	stessa lunghezza e $x \le y$
$e$ o $l$	$b$	$\sqcup$	$\text{no}$	—	—	$y$ più lungo
$e$ o $l$	$\sqcup$	$b$	$\text{no}$	—	—	$x$ più lungo

Prova la soluzione

Nastro 1

▷01;10⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ ▷ -> s ▷ R ▷ R
s b ⊔ -> s b R b R      # copia x
s ; ⊔ -> r ; R ⊔ L      # testina 1 sulla prima cifra di y
r σ b -> r σ S b L      # riavvolge il 2° nastro
r σ ▷ -> e σ S ▷ R      # pronto a confrontare
e b b -> e b R b R      # cifre uguali
e 1 0 -> l 1 R 0 R      # x minore di y
e 0 1 -> no 0 S 1 S     # x maggiore di y
l b b' -> l b R b' R    # ormai conta solo la lunghezza
e ⊔ ⊔ -> yes ⊔ S ⊔ S    # stessa lunghezza e x ≤ y
l ⊔ ⊔ -> yes ⊔ S ⊔ S
e b ⊔ -> no b S ⊔ S     # y più lungo
l b ⊔ -> no b S ⊔ S
e ⊔ b -> no ⊔ S b S     # x più lungo
l ⊔ b -> no ⊔ S b S

Somma binaria senza overflowfunzione · 2 nastri

Nelle tracce: LU22

01+10=11

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$b$	$\sqcup$	$s$	$b, \rightarrow$	$b, \rightarrow$	copia $x$
$s$	$;$	$\sqcup$	$m$	$;, \rightarrow$	$\sqcup, -$	$x$ copiato: la testina 2 aspetta qui
$m$	$b$	$\sqcup$	$m$	$b, \rightarrow$	$\sqcup, -$	scorre $y$
$m$	$\sqcup$	$\sqcup$	$c_0$	$\sqcup, \leftarrow$	$\sqcup, \leftarrow$	fine di $y$ : entrambe sull'ultima cifra
$c_0$	$0$	$0$	$c_0$	$0, \leftarrow$	$0, \leftarrow$	$0 + 0 = 0$
$c_0$	$0$	$1$	$c_0$	$0, \leftarrow$	$1, \leftarrow$	$0 + 1 = 1$
$c_0$	$1$	$0$	$c_0$	$1, \leftarrow$	$1, \leftarrow$	$1 + 0 = 1$
$c_0$	$1$	$1$	$c_1$	$1, \leftarrow$	$0, \leftarrow$	$1 + 1 = 10$ : scrive 0, riporto 1
$c_1$	$0$	$0$	$c_0$	$0, \leftarrow$	$1, \leftarrow$	$0 + 0 + 1 = 1$ : il riporto si esaurisce
$c_1$	$0$	$1$	$c_1$	$0, \leftarrow$	$0, \leftarrow$	$0 + 1 + 1 = 10$
$c_1$	$1$	$0$	$c_1$	$1, \leftarrow$	$0, \leftarrow$	$1 + 0 + 1 = 10$
$c_1$	$1$	$1$	$c_1$	$1, \leftarrow$	$1, \leftarrow$	$1 + 1 + 1 = 11$ : scrive 1, riporto 1
$c_0$	$;$	$\triangleright$	$h$	$;, -$	$\triangleright, \rightarrow$	stessa lunghezza, nessun riporto: $x + y$ è sul 2° nastro
$c_1$	$;$	$\triangleright$	$\text{no}$	—	—	overflow
$c_0$ o $c_1$	$;$	$b$	$\text{no}$	—	—	$x$ più lungo
$c_0$ o $c_1$	$b$	$\triangleright$	$\text{no}$	—	—	$y$ più lungo

Prova la soluzione

Nastro 1

▷01;10⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ ▷ -> s ▷ R ▷ R
s b ⊔ -> s b R b R      # copia x
s ; ⊔ -> m ; R ⊔ S      # x copiato: la testina 2 aspetta qui
m b ⊔ -> m b R ⊔ S      # scorre y
m ⊔ ⊔ -> c0 ⊔ L ⊔ L     # fine di y: entrambe sull'ultima cifra
c0 0 0 -> c0 0 L 0 L    # 0 + 0 = 0
c0 0 1 -> c0 0 L 1 L    # 0 + 1 = 1
c0 1 0 -> c0 1 L 1 L    # 1 + 0 = 1
c0 1 1 -> c1 1 L 0 L    # 1 + 1 = 10: scrive 0, riporto 1
c1 0 0 -> c0 0 L 1 L    # 0 + 0 + 1 = 1: il riporto si esaurisce
c1 0 1 -> c1 0 L 0 L    # 0 + 1 + 1 = 10
c1 1 0 -> c1 1 L 0 L    # 1 + 0 + 1 = 10
c1 1 1 -> c1 1 L 1 L    # 1 + 1 + 1 = 11: scrive 1, riporto 1
c0 ; ▷ -> h ; S ▷ R     # stessa lunghezza, nessun riporto: x + y è sul 2° nastro
c1 ; ▷ -> no ; S ▷ S    # overflow
c0 ; b -> no ; S b S    # x più lungo
c1 ; b -> no ; S b S
c0 b ▷ -> no b S ▷ S    # y più lungo
c1 b ▷ -> no b S ▷ S

Chiave assente dalla listadecisione · 2 nastri

Nelle tracce: SE23, LU24

s

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$c$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$c$	$b$	$\sqcup$	$c$	$b, \rightarrow$	$b, \rightarrow$	copia key
$c$	$,$	$\sqcup$	$r$	$,, \rightarrow$	$\sqcup, \leftarrow$	fine di key
$r$	$\sigma$	$b$	$r$	$\sigma, -$	$b, \leftarrow$	riavvolge il 2° nastro
$r$	$\sigma$	$\triangleright$	$m$	$\sigma, -$	$\triangleright, \rightarrow$	pronto a confrontare
$m$	$\sqcup$	qualsiasi	$\text{yes}$	—	—	lista finita (dopo l'ultima virgola)
$m$	$b$	$b$	$m$	$b, \rightarrow$	$b, \rightarrow$	finora uguali
$m$	$b$	$\bar{b}$ oppure $\sqcup$	$k$	$b, \rightarrow$	(uguale), $-$	cifre diverse, o elemento più lungo di key
$m$	$,$	$b$	$r$	$,, \rightarrow$	$b, \leftarrow$	elemento più corto: diverso
$m$	$,$	$\sqcup$	$\text{no}$	—	—	elemento uguale a key
$k$	$b$	qualsiasi	$k$	$b, \rightarrow$	(uguale), $-$	salta il resto dell'elemento
$k$	$,$	qualsiasi	$r$	$,, \rightarrow$	(uguale), $\leftarrow$	passa al prossimo elemento

Prova la soluzione

Nastro 1

▷01,00,01,⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ ▷ -> c ▷ R ▷ R
c b ⊔ -> c b R b R      # copia key
c , ⊔ -> r , R ⊔ L      # fine di key
r σ b -> r σ S b L      # riavvolge il 2° nastro
r σ ▷ -> m σ S ▷ R      # pronto a confrontare
m ⊔ σ -> yes ⊔ S σ S    # lista finita (dopo l'ultima virgola)
m b b -> m b R b R      # finora uguali
m b b̄ -> k b R b̄ S      # cifre diverse
m b ⊔ -> k b R ⊔ S      # elemento più lungo di key
m , b -> r , R b L      # elemento più corto: diverso
m , ⊔ -> no , S ⊔ S     # elemento uguale a key
k b σ -> k b R σ S      # salta il resto dell'elemento
k , σ -> r , R σ L      # passa al prossimo elemento

SAT-UNSAT con un oracolo SATdecisione · 2 nastri · oracolo SAT

Nelle tracce: F08, G16, E26, ND

x

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$\sigma$	$\sqcup$	$s$	$\sigma, \rightarrow$	$\sigma, \rightarrow$	copia $x$
$s$	$;$	$\sqcup$	$q_?$	$;, -$	$\sqcup, -$	" $x \in \mathrm{SAT}$ ?"
$q_{\text{NO}}$	$;$	$\sqcup$	$\text{no}$	$;, -$	$\sqcup, -$	$x$ insoddisfacibile
$q_{\text{YES}}$	$;$	$\sqcup$	$r$	$;, -$	$\sqcup, \leftarrow$	$x$ soddisfacibile: si passa a $y$
$r$	$;$	$\sigma$	$r$	$;, -$	$\sqcup, \leftarrow$	cancella la query
$r$	$;$	$\triangleright$	$a$	$;, \rightarrow$	$\triangleright, \rightarrow$	query cancellata
$a$	$\sigma$	$\sqcup$	$a$	$\sigma, \rightarrow$	$\sigma, \rightarrow$	copia $y$
$a$	$\sqcup$	$\sqcup$	$q_?$	$\sqcup, -$	$\sqcup, -$	" $y \in \mathrm{SAT}$ ?"
$q_{\text{YES}}$	$\sqcup$	$\sqcup$	$\text{no}$	$\sqcup, -$	$\sqcup, -$	$y$ soddisfacibile
$q_{\text{NO}}$	$\sqcup$	$\sqcup$	$\text{yes}$	$\sqcup, -$	$\sqcup, -$	$x$ sì, $y$ no

Prova la soluzione

Nastro 1

▷(x|y)&!x;x&!x⊔⊔

Nastro 2 (query)

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ ▷ -> s ▷ R ▷ R
s σ ⊔ -> s σ R σ R          # copia x
s ; ⊔ -> q? ; S ⊔ S         # "x ∈ SAT?"
s ⊔ ⊔ -> no ⊔ S ⊔ S         # manca ";" (qui σ non comprende ⊔)
qNO ; ⊔ -> no ; S ⊔ S       # x insoddisfacibile
qYES ; ⊔ -> r ; S ⊔ L       # x soddisfacibile: si passa a y
r ; σ -> r ; S ⊔ L          # cancella la query
r ; ▷ -> a ; R ▷ R          # query cancellata
a σ ⊔ -> a σ R σ R          # copia y
a ⊔ ⊔ -> q? ⊔ S ⊔ S         # "y ∈ SAT?"
qYES ⊔ ⊔ -> no ⊔ S ⊔ S      # y soddisfacibile
qNO ⊔ ⊔ -> yes ⊔ S ⊔ S      # x sì, y no

INDEPENDENT SET con un oracolo CLIQUEdecisione · 2 nastri · oracolo CLIQUE

Nelle tracce: SP

K

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$0$	$\sqcup$	$s$	$0, \rightarrow$	$1, \rightarrow$	inverte il bit: c'è un arco in $\bar G$
$s$	$1$	$\sqcup$	$s$	$1, \rightarrow$	$0, \rightarrow$	inverte il bit: niente arco in $\bar G$
$s$	$,$	$\sqcup$	$s$	$,, \rightarrow$	$,, \rightarrow$	copia il separatore
$s$	$;$	$\sqcup$	$s$	$;, \rightarrow$	$;, \rightarrow$	copia il separatore
$s$	$:$	$\sqcup$	$k$	$:, \rightarrow$	$:, \rightarrow$	fine della matrice
$k$	$b$	$\sqcup$	$k$	$b, \rightarrow$	$b, \rightarrow$	copia $K$ senza cambiarlo
$k$	$\sqcup$	$\sqcup$	$q_?$	$\sqcup, -$	$\sqcup, -$	" $\bar G$ ha una cricca di almeno $K$ nodi?"
$q_{\text{YES}}$	$\sqcup$	$\sqcup$	$\text{yes}$	$\sqcup, -$	$\sqcup, -$	c'è un independent set di almeno $K$ nodi
$q_{\text{NO}}$	$\sqcup$	$\sqcup$	$\text{no}$	$\sqcup, -$	$\sqcup, -$	non c'è

Prova la soluzione

Nastro 1

▷0,1,0;1,0,1;0,1,0:10⊔⊔

Nastro 2 (query)

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Mostra il codice della soluzione

s ▷ ▷ -> s ▷ R ▷ R
s 0 ⊔ -> s 0 R 1 R      # inverte il bit: c'è un arco nel complemento
s 1 ⊔ -> s 1 R 0 R      # inverte il bit: niente arco nel complemento
s , ⊔ -> s , R , R      # copia il separatore
s ; ⊔ -> s ; R ; R
s : ⊔ -> k : R : R      # fine della matrice
k b ⊔ -> k b R b R      # copia K senza cambiarlo
k ⊔ ⊔ -> q? ⊔ S ⊔ S     # "il complemento ha una cricca di almeno K nodi?"
qYES ⊔ ⊔ -> yes ⊔ S ⊔ S # c'è un independent set di almeno K nodi
qNO ⊔ ⊔ -> no ⊔ S ⊔ S   # non c'è