Suggest edit — universal turing machine

Title

Name

Note

---
title: "universal turing machine"
type: concept
related: [Turing Machinea, Deterministic Finite Automata, There Are Non Recognizable Languages]
source: https://www.jemoka.com/posts/kbhuniversal_turing_machine/
confidence: high
status: active
---

bit string encoding encode a finite string in $\Sigma^{*}$ as a bit string: encoding each character in $\log | \Sigma |$ bits (by basically IDing each bit).
For $x \in \Sigma^{*}$, define $b_{\Sigma}(x)$ to be its binary encoding.
For $x,y \in \Sigma^{*}$, to encode the pair of strings $x$ and $y$, we can encode tuples by adding just a separate symbol $\Sigma&rsquo; = \Sigma \cup \qty {,}$, and then we can write $x,y$. (if we want to know how long $x$ is ahead of time we can encode it by show you how long it is through zeros early&mdash;$0^{|b_{\Sigma} (x)|} 1 b_{\Sigma}(x) b_{\Sigma}(y)$.
Turing Machine Encoding we can encode a turing machine just by writing out its each part.
$n$ state count, $m$ tape symbol count (where the first $k$ are input symbols), $s$ start state id, $t$ accept state id, $r$ reject state id, $u$ blank symbol ID, transitions $(p,i), (q,j, D)$ (i.e. start state, start tape, next state, next tape, movement directions)
the key is that this is constant size
being able to encode computation means that we can have languages defined by computation&mdash;
$A_{DFA} = \{(B,w) \mid B$ encodes a DFA over some $\Sigma$, and $B$ accepts $w \in \Sigma^{*}$ $\}$ $A_{NFA} = \{(B,w) \mid B$ encodes a NFA over some $\Sigma$, and $B$ accepts $w \in \Sigma^{*}$ $\}$ $A_{TM} = \{(B,w) \mid B$ encodes a TM over some $\Sigma$, and $B$ accepts $w \in \Sigma^{*}$ $\}$ (we will use a decoding such that any string decodes to a pair $(A,b)$, no matter if its useful or not&mdash;so we don&rsquo;t need to typecheck things; in particular, if there&rsquo;s some $x$ which doesn&rsquo;t decode correctly, we just return $(D, \varepsilon)$ where $D$ accepts nothing and $\varepsilon$ remains to be the empty string.)
This means that:
\begin{equation} \neg A_{TM} = \qty { (M, w) \mid M \text{ does not accept } w} \end{equation}
Universal Turing Machine Theorem There exists a Turing machine $U$ which takes as input:
the code of an arbitrary Turing machine $M$ an input string $w$ such that $U$ accepts $(M,w)$ IFF $M$ accepts $w$. That is, $U$ recognizes $A_{TM}$.
i.e.: $U$ runs every Turing machine (think: programmable computers). Which, btw, isn&rsquo;t true of DFA/NFAs&mdash;the languages $A_{DFA}$ and $A_{NFA}$ is not regular
(in some sense, $U$ is the &ldquo;hardware&rdquo; which drives the corresponding &ldquo;software&rdquo;)
$A_{DFA}$ is decidable Because a DFA is a special case of a Turing Machine. So we can run the Universal Turing machine on it and output its answer (we know DFAs terminate)&mdash;they always accept or reject.
$A_{NFA}$ is decidable perform subset construction, then do what&rsquo;s above (i.e. treat the DFA as a TM)
$A_{TM}$ is recognizable but not decidable We want to show that $A_{TM}$ is recognizable but not decidable; and $\neg A_{TM}$ is not recognizable (since $A_{TM}$ is only recognizable and not decidable, we know that $\neg A_{TM}$ can&rsquo;t even be recognizable; otherwise, we would satisfy L is decidable IFF L and not L are both recognizable and that would make $A_{TM}$ decidable).
$A_{TM}$ is undecidable constructive proof
Suppose we have a $H$ that recognize $A_{TM}$.
\begin{equation} H((M,w)) = \begin{cases} \text{Accept}, \text{if $M$ accepts $W$} \\ \text{Reject or loops}, \text{if $M$ does not accept (including loops) $W$} \\ \end{cases} \end{equation}
let us define a new machine $D$ which runs the encoding of $M$ on $M$: which run $H$ on $(M,M)$ and output the opposite of $H$ if it does halts; otherwise, $D$ keeps looping.
\begin{equation} D(M) = \begin{cases} \text{Reject}, \text{if $M$ accepts $M$} \\ \text{Accept}, \text{if $M$ does not accept $M$} \\ \text{Loops}, \text{if $M$ loops on $M$} \end{cases} \end{equation}
plugging in $D$ for $M$, note that the first two options are still impossible but the last option is possible (&ldquo;D loop if D loops on D&rdquo;). So D must loop on D. Hence, $\qty(D_{h}, D_{h})$ is not in $A_{TM}$ (it loops), yet $H$ loops on it instead of rejecting it. So $A_{TM}$ is undecidable.
contradiction proof
Suppose there is a machine $H$ which decides $A_{TM}$. This means that:
\begin{equation} H((M,w)) = \begin{cases} \text{Accept}, \text{if $M$ accepts $W$} \\ \text{Reject}, \text{if $M$ does not accept (including loops) $W$} \\ \end{cases} \end{equation}
let us define a new machine $D$ which runs the encoding of $M$ on $M$: which run $H$ on $(M,M)$ and output the opposite of $H$ (exists since we assumed that $A_{TM}$ is decidable (terminating)).
\begin{equation} D(M) = \begin{cases} \text{Reject}, \text{if $M$ accepts $M$} \\ \text{Accept}, \text{if $M$ does not accept (including loops) $M$} \\ \end{cases} \end{equation}
In particular, note that this has the same problem of there are non-recognizable languages &mdash; if we ran $D(D)$, if $D(D)$ accepts, we have the property that $D$ didn&rsquo;t accept $D$; if $D(D)$ rejects, then have the property that $D$ accepts $D$. This reaches a contradiction.