Traccia L18

12 luglio 2018

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

0/7

1
$\mathrm{PH} = \mathrm{EXP}$
2
$\mathrm{TIME}(n^3) \subseteq \mathrm{TIME}((2n+1)^9)$
3
$\mathrm{P} \subseteq \mathrm{PH}$
4
$\mathrm{QSAT} \in \mathrm{EXP}$
5
$\mathrm{QSAT}_1 \notin 2\text{-}\mathrm{EXP}$
6
$O(2^{n/2})$
7
$\Pi_4^{\mathrm{P}} \subseteq \mathrm{L}$

Mancano 7 risposte.

Macchina di Turing

x

Il metodo, passo per passo

#	Stato	Legge	Nuovo stato	Scrive	Mossa	Commento
1
2
3

Da controllare

Riga 3: lo stato q non ha righe: lì la macchina si blocca e rigetta

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

Nastro

▷0110⊔⊔⊔

Stato sPasso 0

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

-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)

Eseguila passo per passo

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