Traccia G20v5

23 giugno 2020, versione 5

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

0/7

1
$\mathrm{DP} = \mathrm{NEXP}$
2
$\mathrm{QSAT}_2$
3
$\mathrm{DP} \subseteq \Sigma_3^{\mathrm{P}}$
4
$\mathrm{UP} \subseteq \mathrm{DP}$
5
$Tutti i linguaggi che sono accettati da MdT nondeterministiche sono anche accettati da MdT deterministiche$
6
$L$
7
$\Sigma_1^{\mathrm{P}}$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT che divide una cifra binaria per 4

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

Nastro

▷10110⊔⊔

Stato sPasso 0

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

10110 \to 101

$p$	$\sigma$	$\delta(p, \sigma)$	commento
$s$	$\triangleright$	$(s, \triangleright, \rightarrow)$	supera l'inizio del nastro
$s$	$b$	$(s, b, \rightarrow)$	scorre l'input fino in fondo
$s$	$\sqcup$	$(q, \sqcup, \leftarrow)$	fine input, torna sull'ultima cifra
$q$	$b$	$(r, \sqcup, \leftarrow)$	cancella l'ultima cifra
$r$	$b$	$(t, \sqcup, \leftarrow)$	cancella la penultima cifra
$r$	$\triangleright$	$(z, \triangleright, \rightarrow)$	l'input aveva una sola cifra
$t$	$b$	$(h, b, -)$	è rimasta almeno una cifra: fine
$t$	$\triangleright$	$(z, \triangleright, \rightarrow)$	non è rimasto niente…
$z$	$\sqcup$	$(h, 0, -)$	…quindi scrive 0

Eseguila passo per passo

Input (un numero binario, per esempio 10110)

Nastro

▷10110⊔⊔

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, torna sull'ultima cifra
q b -> r ⊔ L      # cancella l'ultima cifra
r b -> t ⊔ L      # cancella la penultima cifra
r ▷ -> z ▷ R      # l'input aveva una sola cifra
t b -> h b S      # è rimasta almeno una cifra: fine
t ▷ -> z ▷ R      # non è rimasto niente…
z ⊔ -> h 0 S      # …quindi scrive 0