計算可能性理論のpdfをちょっと読んだ。

https://www.kurims.kyoto-u.ac.jp/~terui/cs2020.pdf

今まで計算不可能関数の存在について、任意のプログラムの停止性を判定するプログラムの話からしか知らなくてあまり腑に落ちてなかったのだが、関数全体の空間とプログラム全体の空間の濃度の違いから言う説明があってかなり直感的に納得がいって感動した。

まず、計算可能関数はプログラムで書ける関数であり、任意のプログラムは有限の記号列と考えられる。有限の記号列全体の集合は$\mathbb{N}\cup\mathbb{N}^2\cup\mathbb{N}^3\cup …$であり、これは加算無限である。

一方で関数$\mathbb{N}\to \mathbb{N}$の全体の濃度は無限の整数列全体$\mathbb{N}^\omega$に一致し、これは非加算無限である。従って計算不可能な関数が存在し、それは計算可能な関数よりも圧倒的に多い。

---

ちょっと良い店の焼肉を頂いた。思っていたより数段美味しかった。良い店の良い肉は美味く、また出し方や前菜などの組み合わせを含め体験自体が良いということが分かった。ここ最近の食事で一番楽しかった。

---

2か月くらい下書き状態になっていたブログ記事を完成させた。安易な物理エンジン使用やめよう委員会の者として世に必要な文書が出せたと思っている。

https://chaosplant.tech/tech-notes/page57