Traccia G20v4

23 giugno 2020, versione 4

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

0/7

1
$\mathrm{L} \subset \Sigma_2^{\mathrm{P}}$
2
$È vero che CIRC SAT non è 4- EXP - completo ?$
3
$\mathrm{EXP} \subseteq 4\text{-}\mathrm{EXP}$
4
$\Sigma_3^{\mathrm{P}}$
5
$f(n)$
6
$Il controllo di soddisfacibilità di una formula logica del primo ordine è in coRE$
7
$\Pi_4^{\mathrm{P}}$

Mancano 7 risposte.

Macchina di Turing

2n

Il metodo, passo per passo

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

Input (una stringa di bit, per esempio 100)

Nastro 1

▷100⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

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

x_i \neq x_{n+1-i}

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$a$	$\sqcup$	$s$	$a, \rightarrow$	$I, \rightarrow$	scelta 1: salta la cifra $a$
$s$	$a$	$\sqcup$	$g_a$	$a, \rightarrow$	$\sqcup, -$	scelta 2: confronta $a$ (ricordata nello stato)
$s$	$\sqcup$	$\sqcup$	$\text{no}$	$\sqcup, -$	$\sqcup, -$	nessuna cifra scelta
$g_a$	$b$	$\sqcup$	$g_a$	$b, \rightarrow$	$\sqcup, -$	va in fondo
$g_a$	$\sqcup$	$\sqcup$	$c_a$	$\sqcup, \leftarrow$	$\sqcup, \leftarrow$	torna indietro su entrambi
$c_a$	$b$	$I$	$c_a$	$b, \leftarrow$	$I, \leftarrow$	consuma una tacca per passo
$c_a$	$b \neq a$	$\triangleright$	$\text{yes}$	$b, -$	$\triangleright, \rightarrow$	cifre simmetriche diverse
$c_a$	$b = a$	$\triangleright$	$\text{no}$	$b, -$	$\triangleright, \rightarrow$	questo ramo rigetta

Eseguila passo per passo