ある計算を行う副作用の無い関数、例えば int foo(int x) という関数を考えた場合、この関数の取りうるだろうかという問題を考えてみます。
もちろんint型のサイズがどれだけかに依存するので、ここでは汎用的に入力nビット、出力mビットと置いてみます（チューリングマシンを考えるより、組み合わせ回路を考えた方が良いのかもしれないですが）。
言うまでも無く、入力と出力の関係の種類を考えた場合、2^((2^n)*m)種類のバリエーションが考えられます。
ここで、例えば1bit入力／1bit出力の場合は4種類。これは、「常に0」、「常に1」、「入力をそのまま出力（バッファ）」、「入力の反対を出力（インバータ）」の４種類です。2bit入力／1bit出力の場合は16種類（AND,OR,EX-ORなどロジック回路の２入力１出力のバリエーション展開そのものですが）となります。
が、nを増やしていくと爆発的に増加するのが分かりmはあまり効かない)、32bit入力、1bit出力の場合には、2^(4G)となってしまいます。すなわち、4Gbitのメモリが取りうるすべてのメモリパターン数と同じだけになってしまいます。これは何を意味するのでしょう？。少なくとも4Gbit未満のメモリのコンピュータに置いては、32bitから1bitを求める関数ですら、実装不可能な種類のものが存在することを示しています。冒頭のint foo(int x)をintが32bitマシンで実装する場合、4*32Gbit＝16Gバイトのメモリがないと、実装不可能なものが発生することになります。それにもし16Gバイトのメモリがあったとしても、例えば値を２で割った値を返すとか、インクリメントした値を返すだけとか、きわめて短いメモリ量（プログラム）で記述可能な関数が複数ある以上、そのしわ寄せで、16Gバイトよりメモリが無いと記述不可能な関数が確かに存在しているはずなのです。
この事実はある意味あたりまえなことなのですが、普段あまり気にせずにコンピュータを万能マシンのごとく思い込んでプログラミングしていた私としては少々驚きを覚えるものでした。たかが、intをintで返すだけの副作用の無い関数ごときで実装不可能なものがあるといわれてもピンとこなかったわけです。
ここで、ではnビット入力でmビット出力という関数でもっとも記述困難な関数とはどんなものなのか？という疑問が生じました。
少なくとも、すべての計算結果をテーブル化して、これを参照するコードを書けば、(2^n)*mビット（テーブルサイズ）＋α（テーブルを引くコード）のメモリで実現できそうなので、これが最悪でもワーストケースだと思います（最大の最小値みたいでやな言い回しだなぁ）。
で、どのような場合に、ワーストケースになるのでしょうか？。論理圧縮の世界にはカルノー図なんてものがあります。次元数が増えると計算困難にはなりますが、AND-ORの２段で一気に答えを出す場合においては、理屈の上では最適なはずです。
早い話、カルノー図で隣接している同じbit部分があれば圧縮可能なのだから、カルノー図レベルで0と1が市松模様状に並んでいるものがワーストでは無いかと考えてみました。
ですが、速攻で間違いに気が付きました。カルノー図レベルで0と1が市松模様というのは何の事は無い、パリティービット回路です。確かにAND-ORの２段で一気に答えを出す場合に置いてはO(2^n)で回路規模が爆発するのですが、回路をn段組んでいいのなら1bitづつEX-ORしていけばO(n)で終わります。ツリー状に計算すれば、O(log n)段で、O(n log n)の回路規模です。
チューリングマシン上でプログラムを書く場合も、１bitずつカウントしてもいいし、シフトしながら2bitずつ纏めていって、log n の時間で終わらせることも出来ます。