Traccia G17

23 giugno 2017

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

0/7

1
$\mathrm{P} \neq \mathrm{NP}$
2
$\mathrm{P} \subset \Sigma_3^{\mathrm{P}}$
3
$\Sigma_1^{\mathrm{P}} \subseteq \Sigma_3^{\mathrm{P}}$
4
$\mathrm{coNP} \subseteq \Pi_3^{\mathrm{P}}$
5
$\mathrm{PP} \subset \Pi_3^{\mathrm{P}}$
6
$\Pi_1^{\mathrm{P}}$
7
$f(n)$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT deterministica a 2 nastri che controlla se una stringa è palindroma

Il metodo, passo per passo

#	Stato	Legge₁	Legge₂		Nuovo stato	Scrive₁	Mossa₁	Scrive₂	Mossa₂	Commento
1

Input (una stringa di bit, per esempio 010)

Nastro 1

▷010⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione (riga 1): δ(s, ▷, ▷) = (s, ▷, →, ▷, →) · supera l'inizio dei due nastri

La soluzione del file di questa traccia aggiunge all'inizio un controllo per la stringa vuota: non serve, perché la macchina qui sotto accetta già la stringa vuota.

s

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$b$	$\sqcup$	$s$	$b, \rightarrow$	$b, \rightarrow$	copia l'input
$s$	$\sqcup$	$\sqcup$	$r$	$\sqcup, \leftarrow$	$\sqcup, -$	fine dell'input: la testina 2 resta dopo la copia
$r$	$b$	$\sqcup$	$r$	$b, \leftarrow$	$\sqcup, -$	riavvolge il 1° nastro
$r$	$\triangleright$	$\sqcup$	$c$	$\triangleright, \rightarrow$	$\sqcup, \leftarrow$	testina 1 sulla prima cifra, testina 2 sull'ultima
$c$	$b$	$b$	$c$	$b, \rightarrow$	$b, \leftarrow$	cifre simmetriche uguali
$c$	$b$	$\bar b$	$\text{no}$	$b, -$	$\bar b, -$	cifre simmetriche diverse
$c$	$\sqcup$	$\triangleright$	$\text{yes}$	$\sqcup, -$	$\triangleright, \rightarrow$	finite insieme: palindroma

Eseguila passo per passo