Traccia F05

31 maggio 2016, prova 05

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

0/7

1
$4\text{-}\mathrm{EXP} \subseteq \Sigma_3^{\mathrm{P}}$
2
$\Sigma_1^{\mathrm{P}}$
3
$f(n)$
4
$Esistono linguaggi accettati da MdT nondeterministiche che non sono in RE ?$
5
$GEOGRAPHY appartiene a PP ?$
6
$\mathrm{QSAT}_1$
7
$QSAT è P - hard ?$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT che divide una cifra binaria per 2

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

101 \to 10

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\sqcup$	$(q, \sqcup, \leftarrow)$	fine input
$q$	$b$	$(r, \sqcup, \leftarrow)$	cancella l'ultima cifra
$r$	$b$	$(h, b, -)$	è rimasta almeno una cifra
$r$	$\triangleright$	$(z, \triangleright, \rightarrow)$	non è rimasto niente…
$z$	$\sqcup$	$(h, 0, -)$	…quindi scrive 0

\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 b -> r ⊔ L      # cancella l'ultima cifra
r b -> h b S      # è rimasta almeno una cifra
r ▷ -> z ▷ R      # non è rimasto niente…
z ⊔ -> h 0 S      # …quindi scrive 0