Minimalist encoding of a Turing machine

Consider a Turing machine $M$ with finite sets of states $Q$ and tape symbols $\Gamma$, and a transition function $\delta$. Encode each possible transition $t_j$ in $M$ by a unique prime $p_j$. A transition $t_j$ is determined by $(q_{\text{current}}, s_{\text{current}}, q_{\text{next}}, s_{\text{next}}, d)$, where $q_{\text{current}}, q_{\text{next}} \in Q$, $s_{\text{current}}, s_{\text{next}} \in \Gamma$, and $d \in \{\text{Left}, \text{Right}\}$. Let $$ \alpha_j = f(q_{\text{current}}, s_{\text{current}}, q_{\text{next}}, s_{\text{next}}, d) $$ be a bijective encoding of this 5-tuple as a single natural number via a standard pairing function, such as the Cantor pairing function, composed multiple times. For example, we can assign a unique natural number code to each element of $Q$, $\Gamma$, and $\{\text{Left}, \text{Right}\}$, then use the Cantor pairing function $\pi(x, y) = \frac{1}{2}(x+y)(x+y+1) + y$ as follows:

• $ a = \pi(\text{code}(q_{\text{current}}), \text{code}(s_{\text{current}}))$
• $ b = \pi(\text{code}(q_{\text{next}}), \text{code}(s_{\text{next}}))$
• $ c = \pi(b, \text{code}(d))$
• $\alpha_j = f(q_{\text{current}}, s_{\text{current}}, q_{\text{next}}, s_{\text{next}}, d) = \pi(a, c)$

Define an overall code $$ E(M) = \prod_j p_j^{\alpha_j}, $$ where the product extends over every transition $t_j$ in $M$. Represent $E(M)$ on a binary-only tape by writing its base-10 digits $d_1 \dots d_k$ in binary, including binary delimiters (e.g., "1111") to separate consecutive decimal digits, using a fixed number of bits (e.g., 4 bits) for each decimal digit.

Construct a universal machine $U$ that operates purely in the binary alphabet $\{0, 1\}$ and does the following:

1. Interprets the tape contents as a string of decimal digits $d_1 \dots d_k$ of $E(M)$.
2. Uses long division and repeated subtraction in binary to detect for each prime $p_j$ the largest exponent $\alpha_j$ such that $p_j^{\alpha_j}$ divides $E(M)$.
3. Reconstructs every transition of $M$. This is done by applying the inverse function $f^{-1}$ to each $\alpha_j$ to obtain the original 5-tuple $(q_{\text{current}}, s_{\text{current}}, q_{\text{next}}, s_{\text{next}}, d)$. Since $f$ is bijective, $f^{-1}$ is well-defined.

Step (2) can be carried out via elementary computations in binary: integer division, primality checks, and exponent counting are all partial recursive functions, hence can be computed by some Turing machine on $\{0, 1\}$ alone.

Once $U$ has recovered $\alpha_j$ for each $j$, it obtains the full transition table of $M$ and simulates $M$ step-by-step on a separate work region of the tape. Whenever $M$'s head in state $q_{\text{current}}$ scans symbol $s_{\text{current}}$, the machine $U$ references the $\alpha_j$ that encodes the transition $(q_{\text{current}}, s_{\text{current}}, q_{\text{next}}, s_{\text{next}}, d)$. It writes the correct symbol $s_{\text{next}}$ on the work tape (only 0 or 1, encoding the symbols of $M$ in binary), updates its own internal binary-encoded "state" to match $q_{\text{next}}$, and shifts its simulated head location one cell left or right, also tracked in binary. This process continues until $M$ would halt.

Since $U$ itself is a Turing machine that writes only the symbols 0 and 1 but can perform prime factorization and all associated arithmetic (including encoding/decoding using $f$ and $f^{-1}$), it follows that a machine restricted to writing 0 and 1 can indeed simulate any algorithm.

Therefore, a binary Turing machine is Turing complete.