kosak https://blog.hatena.ne.jp/kosak/ tranquillo https://kosak.hatenadiary.org/ misc Th. 実数の全体を とし、あるチューリング完全な言語で書かれたプログラムの全体を とおくとき、連続体仮説を認めれば （cf. id:succeed:20061121#1164079716）。Prf. 背理法を使う。無限に長い文字列を出力する（つまり、何かを出力し続けて停止しない）ようなプログラムを「無限プログラム」と呼ぶことにして、無限プログラムの全体を とおく。もし が可算であると仮定すると、 も可算であるから、すべての無限プログラムを何らかの順序で列挙することができる。ここで、次のようなプログラムを考える： を にし、 を最初の無限プログラムにする。 の実行をエミュレートして、その出力の… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkosak.hatenadiary.org%2Fentry%2F20061225%2F1167024885" title=" てふてふ - tranquillo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2006-12-25 14:34:45 rich https://kosak.hatenadiary.org/entry/20061225/1167024885 1.0 100%