計算可能性理論とは？わかりやすく解説

計算可能性理論（けいさんかのうせいりろん、英: computability theory）とは、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。

はじめに

理論計算機科学の中心的課題の1つとして、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処する、ということがあった。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし間違っており、そのことは「チューリングマシンの停止問題」の否定的解決として示された。以下では、そこに至る過程とそこから先の発展を述べる。

計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか？」である。この質問はやや難解なので、もう少し判り易く例を挙げる。まず、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。同様に、全ての回文の集合や、文字 'a' だけからなる全ての文字列の集合などが形式言語の例である。これらの例では、それぞれの問題を解くコンピュータの構築の容易さが言語によって異なることは明白である。

しかし、この観測された明白な違いはどういう意味で正確なのか？ある特定の問題をコンピュータで解く際の困難さの度合いを定式化し定義できるか？その質問に答えるのが計算可能性理論の目標である。

計算の形式モデル

計算可能性理論の中心課題に答えるために、「コンピュータとは何か」を形式的に定義する必要がある。利用可能な計算モデルはいくつか存在する。以下に代表例を挙げる。

決定性有限状態機械: 決定性有限オートマトン（DFA）、あるいは単に有限状態機械とも呼ぶ。単純な計算モデルである。現在、実際に使われているコンピュータは、有限状態機械としてモデル化できる。この機械は状態の集合を持ち、入力列によって働く状態遷移の集合を持つ。一部の状態は受容状態と呼ばれる。入力列は一度に1文字ずつ機械に入力され、現在状態から状態遷移先への遷移条件と入力が比較され、マッチングするものがあればその状態が新たな状態となる。入力列が終了したとき機械が受容状態にあれば、全入力列が受容されたということができる。
プッシュダウン・オートマトン: 有限状態機械に似ているが、任意のサイズに成長可能な実行スタックを利用可能である点が異なる。状態遷移の際に記号をスタックに積むかスタックから記号を除くかを指定できる。
チューリングマシン: これも有限状態機械に似ているが、入力が「テープ」の形式になっていて、読むだけでなく書くこともでき、テープを送ったり巻き戻したりして読み書きの位置を決めることができる。テープのサイズは任意である。チューリングマシンは時間さえかければ、かなり複雑な問題も解くことができる。このモデルは計算機科学では最も重要な計算モデルであり、資源の限界がない計算をシミュレートしたものである。