This is an encoding scheme such that all strings are valid output-only Turing machines. We will start by defining L:
3(2x)(2+x) = L
where L is the length of the string or number of bits needed for a fully defined non-halting output-only Turing machine.
Fully defined means that every state has a transition function telling the machine: what to write (w), where to move the tape head (m), and what state to move to (q). If a state is not fully defined than it is in the set F and is a halting state. Therefore, we can determine the total number of states by calculating the length of the string. That number will always be a power of 2, but we can effectively have fewer states by making states that are unreachable.
The tape alphabet, Γ, is {1, 0, ⊔}, but all turing machines encoded this way have an important limitation: they cannot write a ⊔. This limitation does not affect Turing-completness as we will prove later.
Therefore, the output-only Turing machine is a 6-Tuple defined as:
{Q,Γ,b,δ,q0,F}
Consider a Turing machine 𝑀 with finite sets of states 𝑄 and tape symbols Γ, and a transition function 𝛿. Encode each possible transition 𝑡𝑗 in 𝑀 by a unique prime 𝑝𝑗. A transition 𝑡𝑗 is determined by (𝑞current,𝑠current,𝑞next,𝑠next,𝑑), where 𝑞current,𝑞next∈𝑄, 𝑠current,𝑠next∈Γ, and 𝑑∈{Left,Right}. Let 𝛼𝑗=𝑓(𝑞current,𝑠current,𝑞next,𝑠next,𝑑) 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 𝑄, Γ, and {Left,Right}, then use the Cantor pairing function 𝜋(𝑥,𝑦)=12(𝑥+𝑦)(𝑥+𝑦+1)+𝑦 as follows:
Define an overall code
where the product extends over every transition 𝑡𝑗 in 𝑀. Represent 𝐸(𝑀) on a binary-only tape by writing its base-10 digits 𝑑1…𝑑𝑘 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 𝑈 that operates purely in the binary alphabet {0,1} and does the following: Interprets the tape contents as a string of decimal digits 𝑑1…𝑑𝑘 mof 𝐸(𝑀). Uses long division and repeated subtraction in binary to detect for each prime 𝑝𝑗 the largest exponent 𝛼𝑗 such that 𝑝𝛼𝑗𝑗 divides 𝐸(𝑀). Reconstructs every transition of 𝑀. This is done by applying the inverse function 𝑓−1 to each 𝛼𝑗 to obtain the original 5-tuple (𝑞current,𝑠current,𝑞next,𝑠next,𝑑). Since 𝑓 is bijective, 𝑓−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 𝑈 has recovered 𝛼𝑗 for each 𝑗, it obtains the full transition table of 𝑀 and simulates 𝑀 step-by-step on a separate work region of the tape. Whenever 𝑀's head in state 𝑞current scans symbol 𝑠current, the machine 𝑈 references the 𝛼𝑗 that encodes the transition (𝑞current,𝑠current,𝑞next,𝑠next,𝑑). It writes the correct symbol 𝑠next on the work tape (only 0 or 1, encoding the symbols of 𝑀 in binary), updates its own internal binary-encoded "state" to match 𝑞next, and shifts its simulated head location one cell left or right, also tracked in binary. This process continues until 𝑀 would halt.
Since 𝑈 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 𝑓 and 𝑓−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. □
The list of all these turing machines is effectively a list of all computable numbers with many repeats and also many patterns of changing 1s and 0s that are not representative of a number.
Program:
Output: