計算可能性理論で取り扱う関数は可算集合から可算集合への対応に限定する。可算集合は自然数全体の集合と１対１の対応がつく可算無限集合か、有限集合である。したがって、実数関数は計算可能性理論ではそのままの形では取り扱わない。関数といえば、非負整数から非負整数への関数を意味する。(中略)計算の手順は有限アルファベットの記号を用いて、有限長の系列で記述されなければならないので、計算可能な関数全体の集合は可算無限集合である。しかし、非負整数から非負整数への関数全体の集合は実数全体の集合と１対１の対応がつく。自然数全体の集合と実数全体の集合とは１対１の対応がつかないことはカントールの対角線論法を用いて示すことができる。このように２つの集合の濃度の違いから、ほとんどの関数は計算可能ではないことがわかる。数理情報科学事典,朝倉書店,大矢 雅則 ら
別の言い方をすれば、「組み合わせ爆発」とも呼ばれる。これは計算可能性よりも計算量について言われるので、その他の言い方の方がしっくりくる場合もあるだろう。
仮想機械について掘り下げていく。
関数の呼び出しと関数の適用に分けて考える。ここまでは上の文と同じである。
λ関数をネストすることを考えよう。平均の関数のサイズ(アルファベットの並びの長さ)をnとしよう。
すると、λ関数をp回呼び出す場合は最悪の場合、メモリ上のプログラムのサイズはn×pとなる。
nが十分に小さい場合、pが大きくてもメインメモリに収まるであろうが、nが例えば1MBの場合、1000回呼び出せば1GBとなる。
λ関数の場合は、アルファベット(バイナリ)の中から、どこが関数の定義でどこが適用の命令なのかVMが理解していないといけない。それは大変なコード(計算量はnn)である。ex. 手続型言語で関数型言語のインタープリタを書いてみよ。
別の実装では全通り網羅する方法もある。メモリチャンクがある数値に一致すれば、別の状態に書き換える、ことも考えられる。これは項書き換えと呼ばれ、非効率的に思われるが、QEMUなどエミュレータでよく使われている。
項書き換えの問題は文字通り網羅しないといけないので、プログラムサイズが大きくなることである。
プログラミングの基本は全通り埋めていくこと。例えば、掛け算(int,int)を全通り埋めるなら(int)では足りないよね。一番単純な解はi×jなら、iをj回足し算(または逆)すればいい。
λ関数を条件付きの末尾再帰形式にして、予め遷移先を決定しておく。そして、ループの回数をCPUの分岐予測に選ばさせる。そうすると、２〜３種類の関数の組み合わせで、正規表現の実装に近いことができる。