A Universal Turing Machine with 20 Instructions

We construct a universal Turing machine with five states, five symbols and 20 instructions in the standard model: one bi-infinite tape, left and right moves only, finite input on a blank background, and halting at an undefined transition. This improves on our earlier 21-instruction machine and other known machines in this model by Rogozhin and by Neary and Woods which use 22. The saving comes from a redesigned printing and restoration protocol that exploits a parity invariant. A direct compiler, with no intermediate tag system, drives the machine through a queue of unary addresses, periodically rebuilding its program so that the history it traverses stays short. It simulates a fixed source machine halting after t steps on input of length n in O((t+1)(n+t+1)^2) time and O((t+1)(n+t+1)) space. For n = O(t) this is cubic time, though the constants are astronomically large. Lean 4 proofs establish universality, halting equivalence, these bounds, and recovery of the source machine's final configuration.