今度はプログラムをコード化するというお話。つまり、例の０と１の文字列に変換するというものである。ここでおもしろいのは「対」という概念が出てくることである。やはりMLの概念との近似性を感じる。この対は再帰的に使うことができる。つまり対の各要素に対を持ってくることができる。
コード化についてはこの組を使って前回に現れた各プログラムの種類ごとに表記を作り、当てはめているだけである。さて、IsProgram(a)という関数を考えてみる。つまり、aはプログラムの文法的に正しいかどうかという関数であり、これは計算可能かどうかということである。
要するに停止するかしないか？であるが、これは計算可能である。あたりまえだろう。もしこれが計算可能でなければ実行してみなければ、プログラムが文法的に正しいかどうかがわからないということになる。つまりシンタックスエラーといものが実行時しかわからないことになる。そんなことはないのは、まぁ、直感的にもわかる。
ここでは、「文法的に」どうかという話であって、ある処理について正しいかどうかという判定ではない。
つぎに、あるプログラムは停止するかどうかという関数は計算可能かどうか？だが、これは残念ながら計算可能ではない。つまり、計算が停止しない。
この証明に用いるために、カントールの対角線論法という考え方を使用する。
しかし、その前に、可算、非可算の概念について説明がある。Ｘ（集合）が可算とは、Ｎ（自然数）からＸ上への関数fが存在しているということである。
つまり、ｎ番目の要素ということが表現可能かどうかを示している。
例えばＺ（整数）は1→1, 2→-1, 3→2とすればよい。Ｑ（有理数）も整数比で表現可能なので可算である。
では、非可算となにか？そのためには対角線論法が必要だということである。それは次回に。
