Wykład 2020-03-03

• 1. Czy się zatrzyma
• 2. DTM

1. Czy się zatrzyma

Mamy program $P$, który mówi czy się zakończy.

Weźmy $P'(x)$:

1. Uruchom $P$ na wejściu $x$
2. Jeśli $P$ się zakończy to done
3. Oth. zwróć $0$

2. DTM

Deterministyczna Maszyna Turinga

$3+4 =~?$

[>][1][1][1][#][1][1][1][1][ ][ ][ ]...

$\Sigma = \{ 1, \#, \sqcup, \triangleright, X \}$

$Q = \{ q_0 \}$

$\forall{\sigma \in \Sigma \setminus \{\sqcup\}}: \delta(q_0, \sigma) = (q_0, \sigma, \rightarrow)$
$\delta(q_0, \sqcup) = (q_0, \sqcup, \leftarrow)$

$\delta(q_1, \triangleright) = (halt, \triangleright, -)$
$\delta(q_1, \#) = (halt, \sqcup, -)$
$\delta(q_1, 1) = (q_p, \sqcup, \leftarrow)$

$\phi(\overline{x}) = ( x_1 \lor x_2 \lor x_3 ) \land ... \land ( x_n \lor \neg{x_1} \lor x_3 )=$
$c_i \land c_2 \land ... \land c_k$

$c_i = ( x \lor y \lor z )$

Problem plecakowy