Traccia F14

15 giugno 2017, prova 14

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

0/7

1
$È vero che 3-COL non è 3- EXP - hard ?$
2
$\Sigma_2^{\mathrm{P}}$
3
$\mathrm{NPSPACE} \subset \Pi_1^{\mathrm{P}}$
4
$Le risposte a TSP(D) ammettono certificati succinti?$
5
$L \in \mathrm{PP}$
6
$\mathrm{QSAT}_1$
7
$\Pi_1^{\mathrm{P}}$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT che incrementa di 1 una cifra binaria

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, per esempio 1011)

Nastro

▷1011⊔⊔⊔

Stato sPasso 0

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

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)

Eseguila passo per passo

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