サーキットの計算量の様々なクラス 補足1

前回の補足を少しさせて頂きたいと思います。

NC^i,AC^iの定義で、

ユニフォームなサーキットの族{Cn1,Cn2,…}で、多項式のサイズや深さが




という事をお話ししましたが、まず、どうしてこのようなことをやるのかということについて、テキストには書いてありませんが、私の思うところを少しお話ししたいと思いいます。

まず、このブログの3回目に「集合論における整数」という記事で簡単に整数や実数の無限に触れ、濃度という考え方を説明しています。今回はそれにも関係することです。

少し視野を広げてみると現在やっていることは数学基礎論（Wikipedia：http://ja.wikipedia.org/wiki/数学基礎論　を参照のこと）という分野でやっていることにあたります。数学基礎論とは数学の分野ではありますが、比較的新しい分野で、数学自体の基礎を数学によって表現できるか、その限界や方法論を扱っている分野でもあります。

どうでも良いですが、高校三年生の数Ⅲで習う微分方程式などは、フーリエ変換=>ラプラス変換という具合にして代数的に求める方法というのが確立されています。量子力学でももっぱらこういうものを使って軌道の非連続性の説明していたと記憶していますが、どうにも自分が知らないことはどうでも良い事だというように仰る方もいらっしゃるようですので、少し書いてみました。

さて、話を

について戻すと、実数の無限大をωとして扱うと、このωを一つの数として考えて、

　ω，2ω，…

となどどんどん数を増やしていき、ωのω個というのを




　

というように表記します。

サーキットは論理式で表わされ、考えられる論理式を整数に一対一で対応させるようなことを考えると、




というのが、じつは






に対応しているのではないかということは誰の目にも明らかでしょう。


さらに、このように論理式を一対一に対応する整数で表わす（以下これを整数でコーディングすると呼びます）が、この考え方は、ゲーデルが不完全性定理を証明するときに用いた考え方であり、自分自身が正しいかどうかを証明するのには自分自身で証明することはできないという考え方に用います。そういうことから、数学の特に整数を扱う部分への公理系への洞察がなされるという事になります。今回の節の最後に、言語について少し触れるかもしれませんが、ここでいいう言語というのは公理系の別名とも言えます。(どういう表記をするかということにも少し特徴がありますが）