• a bi-infinite tape
• a read/write head
• internal state

• new bit
• new state
• right or left

• $\mathrm{\forall }$ Turing machines $T$,
• $\mathrm{\exists }{c}_T\in \{0,1{\}}^{\ast }$ such that
• $\mathrm{\forall }p\in \{0,1{\}}^{\ast }$,
• $\mathrm{\exists }{p}^{\prime }\in \{0,1{\}}^{\ast }$ such that $U(p^{\prime })=T(p)$
  and
  $|p^{\prime }|\le |p|+|c_T|$.

• for any other programming language $T$
• there's a program $c_T$, called a compiler such that
• for any program $p$ written in $T$,
• there's another program $p^{\prime }$ written in $U$ such that they give the same answer
  and
  $p^{\prime }$ is no longer than concatenating the compiler and the program for $T$.

1. Does this theorem prove that $p$ is elegant for some $x$?
2. Is $|p|>|\text{FAS}|+|\text{theorem examiner}|$?

• Given ${\mathrm{\Omega }}_U$ up to $2^{-m}$, we know the halting status of all programs $\le m$ bits long:
• Run the programs in parallel:

        1
        12
        123
        1234
        1x345
        1 3456
        1 3x567
        1 3 5678
          .
          .
          .
       

1. reads in ${\mathrm{\Omega }}_U[m]$
2. computes the outputs of the halting programs
3. chooses a string $x$ not in that set

   1       1       -
   2      10       0
   3      11       1
   4     100      00
   5     101      01
   6     110      10
   7     111      11
   8    1000     000
   .
   .
   .
   

• If all the information we need is in $s$---that is, $U(s)=\zeta [m]$ ---then $n=1.$
• If $s$ is independent of $\zeta [m]$, then $n$ needs to satisfy $U(\text{bin}(n))=\zeta [m]$ and since $|\text{bin}(n)|>m-c$, $n>2^{-m+c}$.
• The difference between these extremes is the uncertainty, so $\mathrm{\Delta }n\ge 2^{-m+c_U}$.