Turingův stroj \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. |