Универсальные машины Тьюринга

legal $(u, y)=\left[u\right.$ является корректным кодом конфигурации $\left.M_{y}\right]$.

final $(u, y)=[$ legal $(u, y)$ и $u$ является финальной конфигурацией $]$.

$\operatorname {next}(u, v, y)=\left[\right.$ если final $(u, y)$, то $u=v$, иначе $\left.u \vdash_{M_{y}} v\right]$.

$\operatorname {init}^{k}\left(x_{1}, \ldots , x_{k}, y\right)=$ начальная конфигурация $M_{y}$ на входах ($x_{1}, \ldots$, $\left.x_{k}\right)$, закодированная так, как описано выше.

$\operatorname {output}(u, y)=$ выход, содержащийся в $u$, если $u$ является финальной конфигурацией $M_{y}$, и $=0$ в противном случае.

$\operatorname {state}(i, \ell , x)=[x$ является корректным кодом ДМТ $M]$ и $\left[\operatorname {substr}_{\left\{ 0,1\right\} }(x, i\right.$, $\ell +2$) равно $10^{\ell } 1$ и представляет состояние $q_{\ell }$ в $M$ ].

$\operatorname {chstate}(x, i, j)=$ код ДМТ, полученной из $M_{x}$ заменой каждого состояния $q_{i}$ на $q_{j}$, если $x$ является корректным кодом ДМТ $M_{x}$; и $=0$ в противном случае.

$\infty \operatorname {loop}(i, x)=[x$ является корректным кодом ДМТ $]$ и $\left[M_{x}\right.$ не определена в состоянии $q_{i}$ ни для какого символа из $\left.\Gamma \right]$.