A fixed effective binary encoding of deterministic one-tape Turing machines

For this page, a coded deterministic one-tape Turing machine is presented in the normalized numeric form $M=(m,s,n,\tau ),$ where:

• $m\ge 3$, and the state set is $Q_m:=\{0,\dots ,m-1\}$ with start state $0$, accept state $1$, and reject state $2$;
• $n\ge 1$, and the tape alphabet is ${\mathrm{\Gamma }}_n:=\{0,\dots ,n-1\}$ with blank symbol $0$;
• $0\le s<n$, and the input alphabet is ${\mathrm{\Sigma }}_s:=\{1,\dots ,s\}$;
• $\tau$ is a total function $\tau :(Q_m\setminus \{1,2\})\times {\mathrm{\Gamma }}_n\to Q_m\times {\mathrm{\Gamma }}_n\times \{0,1\},$ where the last coordinate encodes the move direction by $0=L,1=R\mathrm{.}$

By Deterministic one-tape Turing machines with designated accept and reject states, each such tuple determines a deterministic one-tape Turing machine, and on this page we use this numeric presentation as the machine description to be encoded.

Let $\mathrm{bin}(r)$ denote the usual binary numeral for a natural number $r$, with $\mathrm{bin}(0)=0$. List the source pairs $(q,a)\in (Q_m\setminus \{1,2\})\times {\mathrm{\Gamma }}_n$ in lexicographic order, and for each such pair write $\tau (q,a)=(q^{\mathrm{\prime }},a^{\mathrm{\prime }},d)\mathrm{.}$ The description tuple of $M$ is the finite tuple of binary words $\mathrm{Desc}(M):=(\mathrm{bin}(m),\mathrm{bin}(s),\mathrm{bin}(n),\mathrm{bin}(q_1^{\mathrm{\prime }}),\mathrm{bin}(a_1^{\mathrm{\prime }}),\mathrm{bin}(d_1),\dots ,\mathrm{bin}(q_N^{\mathrm{\prime }}),\mathrm{bin}(a_N^{\mathrm{\prime }}),\mathrm{bin}(d_N)),$ where $N=(m-2)n$ and the triples are listed in the same lexicographic source order.

For a binary word $w$, put $c(w):=1^{\mathrm{\mid }w\mathrm{\mid }}0w$. For every finite nonempty tuple of binary words define one variable-arity encoder by $E(w_1,\dots ,w_k):=1^{k}0c(w_1)\cdots c(w_k)\mathrm{.}$ The first $0$ recovers the arity $k$, and the self-delimiting blocks then recover the entries. Different arities have different unary headers, so this single encoder is injective and prefix-free across all finite positive arities; for each fixed arity it is the construction from Finite tuples admit effective prefix-free binary encodings.

The chosen code of $M$, written $<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$, is $<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>:=E(\mathrm{Desc}(M))\mathrm{.}$

Its total decoder first parses the unary arity and the indicated self-delimiting blocks. It then checks that every entry is a canonical binary numeral, that the first three entries give $m\ge 3$, $n\ge 1$, and $0\le s<n$, that the arity is $3+3(m-2)n$, and that every transition triple lies in $Q_m\times {\mathrm{\Gamma }}_n\times \{0,1\}$. If every check succeeds, it returns the unique coded machine determined by those data; otherwise it returns a fixed malformed-code symbol. Thus the chosen machine coding is effective in the sense of Effective binary encodings and total decoders.

• This coding fixes one concrete syntax for machine descriptions. Universality on this page is always relative to that syntax.

• The coding describes machines, not the partial functions or languages they induce. Different coded machines may still compute the same mathematical function.