Traccia F01

30 maggio 2016, prova 01

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

0/7

1
$\mathrm{PSPACE} \subseteq \mathrm{NEXP}$
2
$\Pi_2^{\mathrm{P}} \subset \mathrm{EXP}$
3
$\mathrm{P} \neq \mathrm{NP}$
4
$4\text{-}\mathrm{EXP} \neq \mathrm{L}$
5
$SCHÖNFINKEL-BERNAYS SAT decidibile in tempo polinomiale con errore limitato da una MdT quantistica ?$
6
$Le riduzioni per i function problems hanno qualcosa in più?$
7
$È vero che 2-SAT non appartiene a DP ?$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT che accetta gli interi positivi dispari (codificati in complemento a due)

Il metodo, passo per passo

#	Stato	Legge		Nuovo stato	Scrive	Mossa	Commento
1

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

Nastro

▷011⊔⊔⊔⊔

Stato sPasso 0

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

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)

Eseguila passo per passo

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)