Theorem D.31, p.181 — a quasi-linear universal machine exists
OpenQuantumKtSoI.Supplement.theorem_D_31complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing
There is a quasi-linear universal machine : a machine of Definition 3.1 with constants such that, for every machine of Definition 3.1, all strings and every integer ,
This is the existence statement behind the transfer of the symmetry failures to universal machines whose programs name arbitrary machines.
Here is the self-delimiting code (§2.1) of the encoding of .
Formalization Note The statement involves no descriptions, so no glue routine set appears.
Differences from the source:
- encoding: machines of Definition 3.1, their encoding ⌜M⌝ and the programs ⌜M⌝‾w; constants c_a, c′_a ≥ 1 → valid coded machines with the published encoding CodedMachine.encode and programs sd M.encode ++ w (the published self-delimiting code); real constants; the deadline read as a floor; reason: the base mission's representation of machines and its pinned encoding (p.22 for floors)
Preamble
import Mathlib import Definitions.Def_QuantumKtSoI_Supplement_qKtU open Classical
Formal statement
namespace QuantumKtSoI.Supplement /-- **Theorem D.31** (A quasi-linear universal machine; Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.181). There is a quasi-linear universal machine `U_ql`. **Formalization Note** Quasi-linear universality is condition (U-a) of Definition 9.1 (`QuasiLinUniversal`), with the published encoding `⌜M⌝ = CodedMachine.encode` and programs `⌜M⌝‾w = sd ⌜M⌝ ++ w`. It involves no descriptions, so no glue routine set appears. -/ theorem theorem_D_31 : ∃ U : CodedMachine, QuasiLinUniversal U := by sorry end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem D.31, p.181; Definition 9.1, p.117