Traccia LU22

22 luglio 2022

Rispondi prima di leggere la spiegazione. I termini sottolineati offrono un aiuto rapido.

0/7

1
$\mathrm{co\text{-}QSAT}_4$
2
$\mathrm{P} \neq \mathrm{NP}$
3
$L_1$
4
$\mathrm{NPSPACE} \subseteq 4\text{-}\mathrm{EXP}$
5
$\mathrm{L} \subset \Pi_4^{\mathrm{P}}$
6
$\mathrm{P} \subseteq \mathrm{BQP}$
7
$\Sigma_2^{\mathrm{P}} \subseteq \mathrm{coNP}$

Mancano 7 risposte.

Macchina di Turing

x;y

Il metodo, passo per passo

#	Stato	Legge₁	Legge₂		Nuovo stato	Scrive₁	Mossa₁	Scrive₂	Mossa₂	Commento
1

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

Nastro 1

▷01;10⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione (riga 1): δ(s, ▷, ▷) = (s, ▷, →, ▷, →) · supera l'inizio dei due nastri

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

Eseguila passo per passo