Traccia LU24

15 luglio 2024, prova 4

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

0/7

1
$\mathrm{EXP} \subset \mathrm{PP}$
2
$Dire se 3-COL è riducibile a GEOGRAPHY$
3
$f(n)$
4
$Dire se le risposte a test di soddisfacibilità di knowledge base SROIQ (OWL-2) ammettono disqualifiers succinti$
5
$\mathrm{coNP} \subset \mathrm{NEXP}$
6
$\Sigma_1^{\mathrm{P}} \subseteq \mathrm{EXP}$
7
$f_{\mathrm{EXP}}$

Mancano 7 risposte.

Macchina di Turing

\mathit{key}, \mathit{el}_1, \dots, \mathit{el}_n,

Il metodo, passo per passo

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

Input (key e gli elementi, ognuno seguito da una virgola: per esempio 01,1,011,)

Nastro 1

▷01,00,01,⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

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

s

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$c$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$c$	$b$	$\sqcup$	$c$	$b, \rightarrow$	$b, \rightarrow$	copia key
$c$	$,$	$\sqcup$	$r$	$,, \rightarrow$	$\sqcup, \leftarrow$	fine di key
$r$	$\sigma$	$b$	$r$	$\sigma, -$	$b, \leftarrow$	riavvolge il 2° nastro
$r$	$\sigma$	$\triangleright$	$m$	$\sigma, -$	$\triangleright, \rightarrow$	pronto a confrontare
$m$	$\sqcup$	qualsiasi	$\text{yes}$	—	—	lista finita (dopo l'ultima virgola)
$m$	$b$	$b$	$m$	$b, \rightarrow$	$b, \rightarrow$	finora uguali
$m$	$b$	$\bar{b}$ oppure $\sqcup$	$k$	$b, \rightarrow$	(uguale), $-$	cifre diverse, o elemento più lungo di key
$m$	$,$	$b$	$r$	$,, \rightarrow$	$b, \leftarrow$	elemento più corto: diverso
$m$	$,$	$\sqcup$	$\text{no}$	—	—	elemento uguale a key
$k$	$b$	qualsiasi	$k$	$b, \rightarrow$	(uguale), $-$	salta il resto dell'elemento
$k$	$,$	qualsiasi	$r$	$,, \rightarrow$	(uguale), $\leftarrow$	passa al prossimo elemento

Eseguila passo per passo