Konfigurace Turingova stroje ID \pojem{Konfigurace Turingova stroje} (Instantaneous Description ID) je řetězec $X_1X_2\ldots X_{i-1}qX_iX_{i+1}\ldots X_n$ kde
\begin{itemize}
\item $q$ je stav Turingova stroje
\item čtecí hlava je vlevo od $i$--tého symbolu
\item $X_1\ldots X_n$ je část pásky mezi nejlevějším a nejpravějším symbolem různým od prázdného ($B$). S výjimkou v případě, že je hlava na kraji -- pak na tom kraji vkládáme jeden $B$ navíc.
\end{itemize} |