Michael Schroeder · Preprint · Version 1.0 · 25 September 2026 · ORCID 0009-0004-3249-0195

A Universal Turing Machine with 21 Instructions

DOI: 10.5281/zenodo.22957167

Abstract

We construct a deterministic universal Turing machine with five states, five tape symbols and 21 defined instructions, and prove that its simulation uses polynomial time and space. It has one head on one bi-infinite tape, starts from finite input on a uniform blank background, and halts at an undefined transition. The construction modifies the 22-instruction machine of Neary and Woods: a shorter ordinary-symbol printing token, an adjusted delimiter transition and a compatible encoding preserve their parity-based restoration while eliminating one instruction. We give an explicit compiler from ordinary Turing machines, including unbounded growth at both simulated tape boundaries, and prove positive finite simulation and halting equivalence. For each fixed source machine, the bounds are polynomial in its running time and initial represented tape length. A Lean 4 development verifies the literal transition table, the complete reduction and these bounds. A supplement contains exact costs, output recovery and size optimisation.

Paper and Supplement

The paper presents the machine, its compiler and the universality and polynomial resource bounds. The supplement develops exact execution costs, output recovery and size optimisation within the specified encoding family. Keep both PDFs together for their cross-document links.

Lean Proofs and Verification Materials

The complete release includes both PDFs and their LaTeX sources, the Lean 4 development, independent compiler and decoder checks, executable examples, checksums and a single release verifier.

Start with README.md in the archive. The command python3 verify.py rebuilds the 72 Lean modules, audits the 662 written theorem declarations and their axiom dependencies, runs the executable checks and rebuilds both documents. The README gives the required tools; the Lean companion uses Lean 4.32.2 with no external package dependencies.

Citation and file integrity

Schroeder, Michael. A Universal Turing Machine with 21 Instructions. Version 1.0, Zenodo, 2026. DOI: 10.5281/zenodo.22957167. Download the BibTeX citation.

The paper, supplement and ZIP on this site are byte-identical to the published Zenodo files. Download the SHA-256 checksums. The archive contains its own manifests and verification record.

The release is dated 25 September 2026 and was made public on 26 September. Preparation-time references to an unpublished Zenodo draft in the unchanged manuscript describe the earlier checkpoint; the linked Zenodo record is public.

The Result and Its Formalization

The machine has one head on one bi-infinite tape. It starts from a finite encoding on a uniform blank background and halts at an undefined transition. The construction modifies Neary and Woods’ 22-instruction machine, retaining their simulation framework and parity-based restoration with a shorter printing token, an adjusted delimiter transition and a compatible encoding.

Lean verifies the literal transition table and instruction count, the complete reduction from ordinary Turing machines, finite-input universality, halting equivalence, source-output recovery and polynomial time and whole-trace space bounds. The compiler needs no advance bound on the source machine’s running time or future tape use. The size optimisation is proved within a specified family of encodings; it is not a proof that 21 is the minimum possible instruction count for every universal machine.

Acknowledgments

The construction, formalization and preparation of this manuscript benefited from research assistance by AI systems developed by OpenAI. Responsibility for the mathematical claims, implementation and presentation rests with the author. The debt to Neary and Woods’ machine and simulation framework is explicit throughout the paper.