Slovník pojmů (ve vývoji)

\pojem{Turingův stroj (TM)} je  sedmice $M=(Q,\Sigma, \Gamma, \delta,q_0,B,F)$ se složkami:
\begin{itemize}
 \item[$Q$] konečná množina \pojem{stavů}
 \item[$\Sigma$] konečná neprázdná množina \pojem{vstupních symbolů}
 \item[$\Gamma$] množina všech  \pojem{symbolů pro pásku}. Vždy $\Gamma \supseteq \Sigma$, $Q\cap \Gamma=\emptyset$.
 \item[$\delta$] \pojem{přechodová funkce}. $\delta(q,x)=(p,Y,D)$, kde:
 \begin{itemize}
 \item[$q$] $\in Q$ aktuální stav
 \item[$X$] $\in \Gamma$ aktuální symbol na pásce
  \item[$p$] nový stav,  $p\in Q$.
  \item[$Y$] $\in \Gamma$ symbol pro zapsání do aktuální buňky, přepíše aktuální obsah.
 \item[$D$] $\in \{L,R\}$ je \pojem{směr} pohybu hlavy (doleva, doprava).
 \end{itemize}
 \item[$q_0$] $\in Q$  \pojem{počáteční stav}.
  \item[$B$] $\in \Gamma \setminus \Sigma$. Blank. Symbol pro prázdné buňky, na začátku všude kromě konečného počtu buněk se vstupem.
  \item[$F$] $\subseteq Q$ množina \pojem{koncových} neboli \pojem{přijímajících} stavů.
\end{itemize}
Pozn: někdy se nerozlišuje $\Gamma$ a $\Sigma$ a neuvádí se prázdný symbol $B$, tj. pětice.

Turingův stroj $M=(Q,\Sigma, \Gamma, \delta,q_0,B,F)$ \pojem{přijímá jazyk} $L(M)=\{w\in \Sigma^*: q_0w \vm^* \alpha p \beta, p\in F, \alpha,\beta \in \Gamma^*\} $, tj. množinu slov, po jejichž přečtení se dostane do koncového stavu. Pásku (u nás) nemusí uklízet.