てふてふ

misc

Th. 実数の全体を 2${\large\mathbb R} とし、あるチューリング完全な言語で書かれたプログラムの全体を 2${\large\mathbb M} とおくとき、連続体仮説を認めれば 2$|{\large\mathbb{R}}|\le|{\large\mathbb{M}}|（cf. id:succeed:20061121#1164079716）。

Prf. 背理法を使う。無限に長い文字列を出力する（つまり、何かを出力し続けて停止しない）ようなプログラムを「無限プログラム」と呼ぶことにして、無限プログラムの全体を 2${\large\mathbb M}' とおく。もし 2${\large\mathbb M} が可算であると仮定すると、2${\large\mathbb M}' も可算であるから、すべての無限プログラムを何らかの順序で列挙することができる。ここで、次のようなプログラムを考える：

  1. 2$n を 2$1 にし、2$I を最初の無限プログラムにする。
  2. 2$I の実行をエミュレートして、その出力の 2$n 文字目を求める。そして、それとは異なる文字を出力する。
  3. 2$n を 2$n+1 にし、2$I を 2$I の次の無限プログラムにして、手順 2. に戻る。

このプログラムは明らかに無限プログラムであるが、列挙されたどの無限プログラムとも異なった出力をする。これは矛盾であり、2${\large\mathbb M} は可算ではない。

追記: 勘違いする人もいないと思いますが、上のは嘘ですよ。念のため。

要するに、はてなの TeX 記法とやらを使ってみたかったわけで。mimeTeX すげー。