<aside> <img src="/icons/light-bulb_blue.svg" alt="/icons/light-bulb_blue.svg" width="40px" /> HOCAEIT Principle ”Have our cake and eat it too”

</aside>

HOC: To show something is computable, can use any programming language to compute it

EIT: To show something is uncomputable, can show that TMs cannot do it

Universality

Theorem: (Universality) There is a single TM that can simulate all TMs! (”Universal TM”)

Universal TMs roughly equals to “compiler + executor” of programs

Theorem: (Uncomputability)There are functions that are uncomputable

Goal Find $U_{TM}: U_{TM}(M,x) = M(x)$ where $U_{TM}$ is a turing machine

Recall that a Turing Machine is entirely described by the transition functions $\delta:[k] \times \Sigma \to [k]\times \Sigma\times\{L,R,S,H\}$

Let number of states = k

number of symbols = $l$, $\Sigma = \{a_0,a_1,\dots,a_{e-1}\}$

Each transition: $S(i,a) = (j,b,A)$

How can we represent $\delta$ as $\{0,1\}^*$?

We can write done $(k, l, ((0,a_0, \,\, \),(0,a_1, \,\, \),\dots, (k,a_{l-1}, \,\, \_))$

• we will have $k*l$ 5-tuples to represent the transition
• Each 5-tuple will have 5 integers and can be represented as a 01 string
• The list of 5-tuples can be represented as a 01 string
• Thus we can represent $\delta$ using a single binary string, and the length would be $O(kl(logk+logl))$
  • Have $k*l$ tuples, each tuple has 5 integers, so each tuple is $O(logk+logl)$
• A TM M can be represented as a binary string.