Domanda 8 delle tracce

Impara a programmare una macchina di Turing

Qui trovi il metodo per scrivere la tabella delle transizioni, un esempio costruito un passo alla volta e le soluzioni di tutte le macchine uscite nelle tracce. La tua macchina la scrivi e la consegni nella domanda 8 di ogni traccia.

Nastro, testina e stati

\delta

Come leggere una transizione

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

Dall'idea alla tabella in quattro passi

Prima di scegliere gli stati, scrivi in due righe che cosa farà la macchina. Dai uno stato a ogni informazione da ricordare: un bit, un riporto, la fase del calcolo. Controlla i casi limite: input vuoto, overflow, testina che torna all'inizio del nastro. Simula a mano un input piccolo, una transizione alla volta. Nelle simulazioni scritte di questa pagina, la cella tra parentesi quadre è quella sotto la testina e ogni riga è un passo. Quando la tua tabella è pronta, la verifichi sui casi di prova con «Consegna», nella domanda 8 di ogni traccia.

Un blocco che torna spesso: arrivare all'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

La tabella si costruisce in quattro passi, e a ogni passo le righe nuove sono evidenziate. All'ultimo passo puoi eseguire la macchina.

Per aggiungere 1 a un numero binario si parte da destra: ogni 1 finale diventa 0 e il primo 0 diventa 1. Prima, però, la macchina deve arrivare all'ultima cifra, quindi scorre l'input fino alla prima cella vuota e torna indietro di una posizione. È quello che fanno le prime tre righe.

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)

Soluzioni delle tracce

Apri un esercizio per leggere come si risolve e per eseguire la soluzione nel simulatore.

Incremento di 11 tracciafunzione · 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

Input (un numero binario, per esempio 1011)

Nastro

▷1011⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷) = (s, ▷, →) · supera l'inizio del nastro

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 21 tracciafunzione · 1 nastro

Nelle tracce: F13

h

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

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

Prova la soluzione

Input (un numero binario, per esempio 101)

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷) = (s, ▷, →) · supera l'inizio del nastro

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 41 tracciafunzione · 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

Input (un numero binario, per esempio 101)

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷) = (s, ▷, →) · supera l'inizio del nastro

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 22 traccefunzione · 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

Input (un numero binario, per esempio 101)

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷) = (s, ▷, →) · supera l'inizio del nastro

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 41 tracciafunzione · 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

Input (un numero binario, per esempio 10110)

Nastro

▷10110⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷) = (s, ▷, →) · supera l'inizio del nastro

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 24 traccefunzione · 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

Input (un numero binario, per esempio 101)

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷) = (s, ▷, →) · supera l'inizio del nastro

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 due1 tracciafunzione · 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

Input (un numero binario in complemento a due, per esempio 0110)

Nastro

▷0110⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷) = (s, ▷, →) · supera l'inizio del nastro

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 due1 tracciadecisione · 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

Input (un numero binario in complemento a due, per esempio 011)

Nastro

▷011⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷) = (s, ▷, →)

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 nondeterministica3 traccedecisione · 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

Input (una stringa di bit, per esempio 100)

Nastro 1

▷100⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷, ▷) = (s, ▷, →, ▷, →)

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 nastri1 tracciadecisione · 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

Input (una stringa di bit, per esempio 0110)

Nastro 1

▷101⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷, ▷) = (s, ▷, →, ▷, →)

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 nastri2 traccedecisione · 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

Input (una stringa di bit, per esempio 010)

Nastro 1

▷010⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷, ▷) = (s, ▷, →, ▷, →)

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 ≤ y3 traccedecisione · 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

Input (due numeri binari separati da ;, per esempio 01;10)

Nastro 1

▷01;10⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷, ▷) = (s, ▷, →, ▷, →)

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 overflow1 tracciafunzione · 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

Input (due numeri binari della stessa lunghezza separati da ;, per esempio 01;10)

Nastro 1

▷01;10⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷, ▷) = (s, ▷, →, ▷, →)

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 lista2 traccedecisione · 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

Input (key e gli elementi, ognuno seguito da una virgola: per esempio 01,1,011,)

Nastro 1

▷01,00,01,⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷, ▷) = (c, ▷, →, ▷, →)

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 SAT4 traccedecisione · 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

Input (due formule separate da ;, con variabili e i connettivi ! & | e le parentesi: per esempio (x|y)&!x;x&!x)

Nastro 1

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

Nastro 2 (query)

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷, ▷) = (s, ▷, →, ▷, →)

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 CLIQUE1 tracciadecisione · 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

Input (matrice di adiacenza ("," tra gli elementi, ";" tra le righe), poi ":" e K in binario: per esempio 0,1,0;1,0,1;0,1,0:10)

Nastro 1

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

Nastro 2 (query)

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione: δ(s, ▷, ▷) = (s, ▷, →, ▷, →)

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'è