Traccia F02

30 maggio 2016, prova 02

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

0/7

1
$È vero che MAX FLOW non è EXP - hard ?$
2
$L_1 \le L_2$
3
$È vero che CLIQUE non appartiene a NEXP ?$
4
$coNP non è strettamente contenuto in L ?$
5
$\mathrm{EXP} = \Pi_1^{\mathrm{P}}$
6
$f(n)$
7
$\mathrm{co\text{-}QSAT}_2$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT che calcola il resto della divisione per 2 di 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 101)

Nastro

▷101⊔⊔⊔⊔

Stato sPasso 0

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

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)

Eseguila passo per passo

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