万能Turingマシンについてのメモ
面倒なので1変数関数を考える
$ \Gamma = \{0,1\}として，クリーネ閉包$ \Gamma^* = \{\emptyset, 0,1,00,01,11,\cdots\} TODO: チューリングマシンの出力とはなにか
$ f:\Gamma^* \mapsto \Gamma^*について，次のような条件を満たすチューリングマシン$ Tが存在するなら，$ fを計算するチューリングマシンであると言う．
入力$ x \in \frak{D}(f)を受け取ると，受理して，$ f(x)を出力する
入力$ x \notin \frak{D}(f)を受け取ると，非受理
チューリングマシン$ Tについて，$ T(x)を$ Tが入力$ xを受け取った際の出力（受理/決定可能）あるいは未定義（非受理あるいは決定不能）を指す．
未定義であること$ uで示すとすると$ T: \Gamma^* \mapsto \Gamma^* \cup \{u\}
Turingマシンは二進の列に（あるいは少なくとも$ \Gammaの列）にエンコードできる つまり適当なチューリングマシン$ T = 01010100101 \cdotsみたいな感じで
では$ Tを入力に取るチューリングマシンを考えれば…？
関数$ \etaを次のように定める
$ \eta(p,x)
$ =T(x)（$ pがあるチューリングマシン$ Tとして有効なコードなら）
$ =0（$ Tがチューリングマシンのコードでないなら）
今これは，適当なチューリングマシンを引数に取ると勝手に計算してくれる万能な関数である（解釈関数） これができるのは，チューリングマシンが適当な記号列$ pにエンコードできるからの芸当である
これは存在する．
今，$ Tは$ \Gamma^* \mapsto \Gamma^* \cup \{u\}だった
つまり$ T(x)が未定義の場合がある
結果として，$ T_Uも$ \Gamma^* \mapsto \Gamma^* \cup \{u\}である
他方，$ \etaは$ \Gamma^* \mapsto \Gamma^*である（べき）
これを修正したい
関数$ \eta'を次のように定める
$ \eta'(p,x)
$ =T(x)（$ pがあるチューリングマシン$ Tとして有効なコードかつ，$ T(x)がまさに決定可能であるとき）
$ =0（それ以外）
こうすると，確かに$ \eta': \Gamma^* \mapsto \Gamma^*．
しかし，これをエミュレートするチューリングマシンは存在しない
$ \eta'はチューリングマシン計算不可能
仮に存在すると仮定すると矛盾をきたすという背理法で証明する