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

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

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

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

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

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

$\operatorname {state}(i, \ell , x)=[x$ является корректным кодом ДМТ $M]$ и $[\operatorname {substr}_{\left\{ 0,1\right\} }(x, i, \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$ является корректным кодом ДМТ $]$ и $[M_{x}$ не определена в состоянии $q_{i}$ ни для какого символа из $\Gamma ]$.