Universal Turing Machines

$\operatorname {legal}(u, y)=\left[u\right.$ is a legal code of a configuration of $\left.M_{y}\right]$.

$\operatorname {final}(u, y)=[\operatorname {legal}(u, y)$ and $u$ is a final configuration $]$.

$\operatorname {next}(u, v, y)=\left[\right.$ if $\operatorname {final}(u, y)$ then $u=v$ else $\left.u \vdash_{M_{y}} v\right]$.

$\operatorname {init}^{k}\left(x_{1}, \ldots , x_{k}, y\right)=$ the initial configuration of $M_{y}$ on inputs ($x_{1}, \ldots$, $\left.x_{k}\right)$, encoded as described above.

$\operatorname {output}(u, y)=$ the output in $u$ if $u$ is a final configuration of $M_{y}$, and $=0$ otherwise.

$\operatorname {state}(i, \ell , x)=[x$ is a legal code of a DTM $M]$ and $\left[\operatorname {substr}_{\left\{ 0,1\right\} }(x, i\right.$, $\ell +2$) is equal to $10^{\ell } 1$ and represents a state $q_{\ell }$ in $M$ ].

$\operatorname {chstate}(x, i, j)=$ the code of a DTM which is obtained from $M_{x}$ by changing each state $q_{i}$ to $q_{j}$, if $x$ is a legal code of a DTM $M_{x}$; and it is $=0$, otherwise.

$\infty \operatorname {loop}(i, x)=[x$ is a legal DTM code $]$ and $\left[M_{x}\right.$ is undefined at state $q_{i}$ on any symbol in $\left.\Gamma \right]$.