Slovník pojmů (ve vývoji)

\pojem{Palindrom} je řetězec $w$ stejný při čtení zepředu i zedadu, tj. $w=w^R$.

Jazyk palindromů není regulární, je bezkontextový.

\pojem{Podmnožinová konstrukce} začíná s NFA $N=(Q_N,\Sigma,\delta_N,q_0,F_N)$. Cílem je popis deterministického DFA $D=(Q_D,\Sigma,\delta_D,\{q_0\},F_D)$, pro který $L(N)=L(D)$.
\begin{itemize}
\item $Q_D$ je množina podmnožin $Q_N$, $Q_D={\cal P}(Q_N)$ (potenční množina). {\footnotesize Nedosažitelné stavy můžeme vynechat.}
\item $F_D=\{S: S\in {\cal P}(Q_N)\ \&\ S \cup F_N \neq \emptyset\}$, tedy $S$ obsahuje alespoň jeden přijímající stav $N$.
\item Pro každé $S\subseteq Q_N$ a každý vstupní symbol $a\in \Sigma$,
$\delta_D(S,a)=\bigcup_{p \in S}\delta_N(p,a)\hbox{.}$
\end{itemize}

Jazyk $L$ je rekurzivní, právě když $L$ i $\overline{L}$ (doplněk) jsou rekurzivně spočetné.

Instance \pojem{Postova korespondenčního problému (PCP)} jsou dva seznamy slov nad abecedou $\Sigma$ značené $A=w_1,w_2,\ldots, w_k$ a $B=x_1,x_2,\ldots, x_k$ stejné délky $k$. Pro každé $i$, dvojice $(w_i,x_i) $ se nazývá \pojem{odpovídající} dvojice.

Instance PCP \pojem{má řešení}, pokud existuje posloupnost jednoho či více přirozených čísel ${i_1}, {i_2}, \ldots, {i_m}$ tak že $w_{i_1}, w_{i_2}, \ldots, w_{i_m}=x_{i_1}, x_{i_2}, \ldots, x_{i_m} $ tj. dostaneme stejné slovo.
V tom případě říkáme, že posloupnost ${i_1}, {i_2}, \ldots, {i_m}$  \pojem{je řešení}.

\pojem{Postův korespondenční problém} je: Pro danou instanci PCP, rozhodněte, zda má řešení.

Problém zastavení TM (halting problem) je algoritmicky nerozhodnutelný.

Neexistuje algoritmus, který by pro daný kód TM a daný vstup rozhodl, zda se TM zastaví.