Invariance theorem for prefix complexity

Dovetail the computations of $M_e$ on all inputs. Whenever a convergence $M_e(p)=x$ first appears, retain it only if $p$ is prefix-comparable with no previously retained input for that same $e$. The retained graph defines a partial computable machine ${\widehat{M}}_e$ with prefix-free domain. If $M_e$ already has prefix-free domain, no convergence is discarded, so ${\widehat{M}}_e=M_e$.

Choose a computable prefix-free self-delimiting code $a_e$ (for example $1^{e}0$) and set $U(a_{e}p)={\widehat{M}}_e(p)$. The universal simulation supplied by Universal and acceptable numberings, together with the effective filter in step 1.1, makes $U$ partial computable.

Distinct $a_e$ are prefix-free and each ${\widehat{M}}_e$ has prefix-free domain, so the domain of $U$ is prefix-free. For every prefix-free machine $M=M_e$, step 1.1 gives ${\widehat{M}}_e=M_e$, and therefore $K_U(x)\le K_M(x)+\mathrm{\mid }{a}_e\mathrm{\mid }$. Thus $U$ is optimal by Prefix-free machines and prefix complexity.