http://www.hyuki.com/d/200610.html#i20061002121646にある「サイコロプログラム・クイズ」に関して。
問題は“どんなサイコロプログラムを作ったとしても、そのサイコロプログラムでは作り出せないサイコロ列が存在することを示せ。”ですが、どんなサイコロ列でも作り出せるプログラムの存在について考えてみます。
まず、nを六進数表記にします。そうすると(0,1,2,3,4,5)の6種類の数字を使って表記することになりますが、これをサイコロの1〜6の整数に一対一対応させます。対応させる方法は6!通りありますが、なるべくわかりやすくする為に、1〜5は同じ数字に、0は6に対応させます。
それから、nの値の1の位をSの1項目、10の位をSの2項目になるような変換方法を定義します。この変換方法にしたがって作ったサイコロプログラムは、入力nに応じて以下のようなサイコロ列Sを作り出すことができます。無限個の数を書くことは出来ないので、サイコロ列は最初の10個を表記します。
n = 1 のとき S =《1, 6, 6, 6, 6, 6, 6, 6, 6, 6, ...》
n = 2 のとき S =《2, 6, 6, 6, 6, 6, 6, 6, 6, 6, ...》
n = 244 のとき S =《4, 4, 2, 6, 6, 6, 6, 6, 6, 6, ...》
n = 2323 のとき S =《3, 2, 3, 2, 6, 6, 6, 6, 6, 6, ...》
nの桁が有限の場合は、0が上位の桁にあるものとして6を導き出します。nの桁数が多くすることで以下のようにいくらでも好きなSの値を指定することができます。
n = 4052431510 のとき S =《6, 1, 5, 1, 3, 4, 2, 5, 6, 4, ...》
n = ...105234105243 のとき S =《3, 4, 2, 5, 6, 1, 3, 4, 2, 5, ...》
Sからnを導き出すことも出来ます。
S =《1, 3, 2, 3, 6, 5, 3, 1, 4, 5, ...》のとき n = ...5431503231
任意のnから一意のSを導き出すことができ、逆に任意のSに対しても一意のnを導き出すことが可能です。つまりnとSは一対一対応していると考えることができます。
つまり、このプログラムによりどんなサイコロ列でも作り出すことが出来るというわけです。
同じ方法を使うことで、自然数と実数を一対一対応させることが出来ます。対角線論法に対する反例というわけです。
蛇足
「分かる人」には説明するまでもないでしょうが、上に書いたことには間違いがあります。でも、それを人に説明するのは難しいのではないでしょうか。
整数の桁数が無限であるとしたところに問題があるというのは比較的わかりやすい説明のように思います。しかし、それでは桁数を無限にした数を使えば、上の話が成り立つのでしょうか。
