A universal Turing machine relative to a fixed machine encoding

Fix the machine coding $<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$ from A fixed effective binary encoding of deterministic one-tape Turing machines. For a binary word $z$, write $c(z):=1^{\mathrm{\mid }z\mathrm{\mid }}0z\mathrm{.}$ Encode a pair of binary words $(x,y)$ by the self-delimiting binary word $⟨x,y⟩:=1^{\mathrm{\mid }x\mathrm{\mid }}0xy\mathrm{.}$ If $v=a_1\cdots a_{\mathrm{\ell }}$ is a finite word whose symbols are natural numbers, write $\widehat{v}:=c(\mathrm{bin}(\mathrm{\ell }))c(\mathrm{bin}(a_1))\cdots c(\mathrm{bin}(a_{\mathrm{\ell }}))\mathrm{.}$

A deterministic one-tape Turing machine $U$ with input alphabet $\{0,1\}$ is a universal Turing machine for the chosen coding if, for every coded deterministic one-tape machine $M=(m,s,n,\tau )$, every input word $w\in {\mathrm{\Sigma }}_s^{\ast }$, and every output word $u$ of $M$, the following hold:

• if $M$ halts on input $w$ with output $u$, then $U$ halts on input $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩$ with output $\widehat{u}$;
• if $M$ diverges on input $w$, then $U$ diverges on input $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩$.

• Universality is relative to one specified description format. Changing the coding changes which input words represent machine/input pairs.

• The definition asks $U$ to reproduce both halting outputs and divergence; it is an interpreter, not a halting decider. No condition is imposed when the simulated machine halts in a configuration that has no output word under the page's strict output convention.