計算けいさん理論りろん

計算けいさん理論りろん（けいさんりろん、Theory Of Computation）または計算けいさん論ろんは、理論りろん計算けいさん機き科学かがくと数学すうがくの一部いちぶで、計算けいさん模型もけいやアルゴリズムを理論りろん的てきにあつかう学問がくもんである。計算けいさん複雑ふくざつ性せい理論りろん、計算けいさん可能かのう性せい理論りろんを含ふくむ。ここでいう計算けいさん（Computation）とは、数学すうがく的てきに表現ひょうげんできる、あらゆる種類しゅるいの情報処理じょうほうしょりのこと。

計算けいさんを厳密げんみつに研究けんきゅうするため、計算けいさん機き科学かがくでは計算けいさん模型もけいと呼よばれるコンピュータの数学すうがく的てき抽象ちゅうしょう化かを行おこなう。その手法しゅほうはいくつかあるが、最もっとも有名ゆうめいなものはチューリングマシンである。チューリングマシンは、言いってみれば無限むげんのメモリを持もつコンピュータであるが、一いち度どにアクセスできるメモリ範囲はんいは非常ひじょうに限かぎられている。チューリングマシンは十分じゅうぶんな計算けいさん能力のうりょくを持もつモデルでありながら、単純たんじゅんで定式ていしき化かしやすく、様々さまざまな証明しょうめいに使つかい易やすいため、計算けいさん機き科学かがく者しゃがよく利用りようする。無限むげんのメモリというのは非ひ現実げんじつ的てきな特徴とくちょうと思おもわれるかもしれないが、より適切てきせつな表現ひょうげんを使つかうならば「無む制限せいげん」のメモリであって、読よみ書かきしようとした時ときにそれができればよく、それに対応たいおうする「無限むげんな実体じったい」とでも言いうべきものが必要ひつようなわけではない。「チューリングマシンで、ある問題もんだいが解とける」とは必かならず有限ゆうげんのステップで計算けいさんが終了しゅうりょうすることを意味いみし、よってそれに必要ひつようなメモリの量りょうは有限ゆうげんである。よって、チューリングマシンで解とくことが出来できる問題もんだいは、現実げんじつのコンピュータであっても必要ひつようなだけのメモリがあれば解とくことが出来できる。

計算けいさん可能かのう性せい理論りろん

詳細しょうさいは「計算けいさん可能かのう性せい理論りろん」を参照さんしょう

計算けいさん可能かのう性せい理論りろんは、ある問題もんだいがコンピュータで解とくことができるかどうかを扱あつかう。チューリングマシンの停止ていし問題もんだいは計算けいさん可能かのう性せい理論りろんにおける、ある意味いみで最もっとも重要じゅうような成果せいかである。定式ていしき化かしやすく、かつチューリングマシンで解とけない問題もんだいの具体ぐたい例れいであり、数学すうがく基礎きそ論ろんとの関係かんけいもある。同時どうじに、静的せいてきに無限むげんループの検出けんしゅつを確実かくじつに行おこなう方法ほうほうは無ないことを示しめしている、といったように実じつ応用おうよう的てきな意義いぎもある。

計算けいさん複雑ふくざつ性せい理論りろん

詳細しょうさいは「計算けいさん複雑ふくざつ性せい理論りろん」を参照さんしょう

計算けいさん複雑ふくざつ性せい理論りろんは、問題もんだいがコンピュータで解とけるかどうかだけでなく、その問題もんだいの困難こんなんさを扱あつかう。時間じかん計算けいさん量りょうと空間くうかん計算けいさん量りょうという2つの観点かんてんがある。時間じかん計算けいさん量りょうとは計算けいさんにかかるステップ数すう、空間くうかん計算けいさん量りょうは計算けいさんに必要ひつようとされるメモリ量りょうに相当そうとうする。

あるアルゴリズムが必要ひつようとする時間じかんと空間くうかんを分析ぶんせきするため、時間じかんや空間くうかんを問題もんだいの入力にゅうりょく量りょうの関数かんすうとして表現ひょうげんする。例たとえば、長ながい数列すうれつから特定とくていの数かずを見みつけ出だすという問題もんだいは、数列すうれつが長ながくなればなるほど難むずかしくなる。数列すうれつに $n$個この数かずがあるとき、その数列すうれつがソートされていなければ、一いち個こ一いち個この数かずを確認かくにんしていくしかない。この場合ばあい、この問題もんだいの解法かいほうの時間じかん計算けいさん量りょうは入力にゅうりょく量りょうに比例ひれいして増大ぞうだいするといえる。

これを単純たんじゅん化かするため、O記法きほうが使つかわれる。こうすることで特定とくていのマシンの実装じっそうを前提ぜんていとすることなく、問題もんだいの本質ほんしつ的てきな計算けいさん量りょうを扱あつかうことができる。従したがって、上うえの例れいの時間じかん計算けいさん量りょうは $O(n)$ となる。

計算けいさん機き科学かがくの中なかでも最もっとも重要じゅうような未み解決かいけつの問題もんだいは、NPと呼よばれる計算けいさん複雑ふくざつ性せいクラスの問題もんだいが効率こうりつ的てきに解とけるかどうかである。詳くわしくは、P≠NP予想よそうを参照さんしょうして欲ほしい。

計算けいさんモデル

詳細しょうさいは「計算けいさんモデル」を参照さんしょう

ここでは例れいとして、計算けいさん可能かのう性せいがチューリングマシンと同等どうとうな計算けいさんモデル（「チャーチ＝チューリングのテーゼ」の記事きじを参照さんしょう）のいくつかを示しめす。

ラムダ計算けいさん

計算けいさんを1つの初期しょきラムダ式しき（入力にゅうりょくを分離ぶんりしたい場合ばあいは2つのラムダ式しき）と有限ゆうげん個このラムダ項こうで表あらわす。各かくラムダ項こうは前まえのラムダ項こうにβべーた簡約かんやくを適用てきようしたものである。

組合くみあわせ論理ろんり

ラムダ計算けいさんとよく似にているが、例たとえばラムダ計算けいさんでは正規せいきの形式けいしきではない不動点ふどうてん演算えんざん子こ Y は組合くみあわせ論理ろんりでは正規せいきに組くみ込こまれているといった違ちがいがある。

μみゅー再帰さいき関数かんすう

複数ふくすうの自然しぜん数すうを引数ひきすうとして1つの自然しぜん数すうを返かえす関数かんすうであり、原始げんし再帰さいき関数かんすうに基もとづいて構築こうちくされ、それにμみゅー再帰さいきを施ほどこしたもの。

マルコフアルゴリズム

文字もじ列れつに一種いっしゅの文法ぶんぽう規則きそくを適用てきようする文字もじ列れつ書かき換かえ系けい。

レジスタマシン

コンピュータを抽象ちゅうしょう化かしたもの。多おおくの場合ばあい、無限むげんサイズの自然しぜん数すうを格納かくのうできるレジスタを持もち、命令めいれい数すうは非常ひじょうに少すくない。チューリングマシンと比較ひかくすると無限むげんのメモリが欠かけているが、レジスタが無限むげんサイズの自然しぜん数すうを格納かくのうできるので、それで代替だいたいされる。

P′′

（en:P′′）チューリングマシンと同様どうよう、無限むげん長ちょうのテープに記号きごうを記録きろくするが、チューリングマシンにおける有限ゆうげん状態じょうたいオートマトンに相当そうとうするものを、固定こてい長ちょうでループの記述きじゅつが可能かのうな命令めいれいの列れつによって記述きじゅつする。これを元もとに、命令めいれいセットを理論りろん向むけから実装じっそう向むけに大幅おおはばにアレンジして設計せっけいされたプログラミング言語げんごがBrainfuckである。

計算けいさん理論りろんは、チューリングマシンより弱よわい（制限せいげんされた）計算けいさんモデルを対象たいしょうとすることもある。これらに関かんする理論りろんを、「オートマトン(の)理論りろん」と呼よぶことがある（この文脈ぶんみゃくでは「オートマトン」とは、チューリングマシンより弱よわい（制限せいげんされた）機械きかいの総称そうしょうである）。

正規せいき表現ひょうげんは文字もじ列れつパターンを指定していするのによく使つかわれる。また、それと等価とうかな有限ゆうげんオートマトンは回路かいろ設計せっけいなどに使つかわれる。文脈ぶんみゃく自由じゆう文法ぶんぽうはプログラミング言語げんごの構文こうぶんを定義ていぎするのに使つかわれる。非ひ決定けってい性せいプッシュダウン・オートマトンは文脈ぶんみゃく自由じゆう文法ぶんぽうと等価とうかである。原始げんし再帰さいき関数かんすうは再帰さいき関数かんすうのサブクラスを定義ていぎしたものである。モデルが異ことなれば得意とくい分野ぶんやも異ことなる。

また、形式けいしき言語げんごとその文法ぶんぽうと、計算けいさんモデルとの間あいだには対応たいおうする関係かんけいがあり、計算けいさん可能かのう性せい＝表現ひょうげん力りょくについて包含ほうがん関係かんけいがあることが知しられている。チョムスキー階層かいそう及および形式けいしき言語げんごの階層かいそうの記事きじを参照さんしょうのこと。

参考さんこう文献ぶんけん

• マイケル・シプサ、『計算けいさん理論りろんの基礎きそ』、渡辺わたなべ 治おさむ 他た訳やく、共立きょうりつ出版しゅっぱん、2000年ねん、ISBN 4-320-02948-8
  • Michael Sipser (2006年ねん). Introduction to the Theory of Computation 2ed. PWS Publishing. ISBN 0-534-94728-X  Part Two: Computability Theory, chapters 3–6, pp.123–222.
• Eitan Gurari (1989年ねん). An Introduction to the Theory of Computation. Computer Science Press. ISBN 0-7167-8182-4  無料むりょう版ばんはこちら: http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html
• Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. 入門にゅうもん書しょ
• Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 2ed Reading, MA: Addison-Wesley, 2001.
• Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998. 上級じょうきゅう者しゃ向むけ
• Hartley Rogers, Jr, Theory of Recursive Functions and Effective Computability, MIT Press, 1987, ISBN 0-262-68052-1
• Computability Logic: 対話たいわ型がた計算けいさんの理論りろん。