この記事には複数の問題があります。改善やノートページでの議論にご協力ください。

出典がまったく示されていないか不十分です。内容に関する文献や情報源が必要です。（2021年3月）


出典は脚注などを用いて記述と関連付けてください。（2017年10月）
出典検索?: "計算可能性理論" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL

この記事は、全部または一部が他の記事や節と重複しています。 具体的には再帰理論との重複です。記事のノートページで議論し、
重複箇所を重複先記事へのリンクと要約文にする（ウィキペディアの要約スタイル参照）か

重複記事同士を統合する（ページの分割と統合参照）か

重複部分を削除して残りを新たな記事としてください。
（2023年12月）

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

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

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

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

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

これらの計算モデルについて、その限界を定めることができる。すなわち、どのクラスの形式言語をその計算モデルは受容するか、である。
有限状態機械の能力

有限状態機械が受容する言語のクラスを正規言語と呼び、正規文法で記述される。有限状態機械が持つことができる状態は有限個であるためであり、正規言語でない言語を扱うには無限の状態数を扱える必要がある。

正規言語でない言語の例として、文字 'a' と 'b' から構成され、各文字列に必ず 'a' と 'b' が同数含まれている言語がある。この言語が有限状態機械で認識できない理由を調べるため、まずこの言語を受容するための有限状態機械 M {\displaystyle M} があるとする。 M {\displaystyle M} は n {\displaystyle n} 個の状態を持つとする。ここで、文字列 x {\displaystyle x} が ( n + 1 ) {\displaystyle (n+1)} 個の 'a' の後に ( n + 1 ) {\displaystyle (n+1)} 個の 'b' があるような構成であるとする。

M {\displaystyle M} の状態数は n {\displaystyle n} しかないため、 x {\displaystyle x} を入力としたときに最初の 'a' が連続する部分の長さが ( n + 1 ) {\displaystyle (n+1)} であることから、鳩の巣原理により、何らかの状態を繰り返すことになる。 ( n + 1 ) {\displaystyle (n+1)} 個の 'a' を読み込んだ状態 S {\displaystyle S} が 'a' を d {\displaystyle d} 個読み込んだ時に再度現われるとする（ d > 0 {\displaystyle d>0} とする）。つまり、 ( n + d + 1 ) {\displaystyle (n+d+1)} 個の 'a' を読み込んだときと ( n + 1 ) {\displaystyle (n+1)} 個の 'a' を読み込んだときの状態が区別されない。従って、 M {\displaystyle M} が x {\displaystyle x} を受容するなら、その機械は ( n + d + 1 ) {\displaystyle (n+d+1)} 個の 'a' と ( n + 1 ) {\displaystyle (n+1)} 個の 'b' からなる文字列も受容してしまう。しかしその文字列は 'a' と 'b' が同数でないため、言語の定義からは受容してはいけない文字列なのである。

従って、この言語は有限状態機械では正しく受容できず、正規言語ではないということになる。これを一般化したものを正規言語の反復補題と呼び、各種言語クラスが有限状態機械で認識できないことを示すのに使われる。

この言語を認識できるプログラムは簡単に書けると思われるかもしれない。そして、現在のコンピュータは有限状態機械でモデル化できると上に書いてある。もちろんプログラムは書けるが、この問題の本質はメモリ容量の限界の見極めにある。非常に長い文字列を与えられた場合、コンピュータのメモリ容量が足りなくなって入力文字数を数えられなくなり、オーバーフローするだろう。その意味で、現代のコンピュータは有限状態機械と同じと言える。したがって、この言語の文字列の大部分は認識できるとしても、必ず認識できない文字列が存在する。
プッシュダウン・オートマトンの能力

プッシュダウン・オートマトンが受容する言語のクラスを文脈自由言語と呼び、文脈自由文法によって記述される。正規言語でないとされた 'a' と 'b' を同数含む文字列からなる言語はプッシュダウン・オートマトンで判定可能である。また一般に、プッシュダウン・オートマトンを有限状態機械のように動作させることもできるので、正規言語も判定可能である。従ってこの計算モデルは有限状態機械よりも強力である。

しかし、プッシュダウン・オートマトンでも判定できない言語がある。その詳細は（正規言語のときとあまり変わらないので）ここでは述べない。文脈自由言語の反復補題も存在する。例えば、素数の集合からなる言語がその例である。
チューリングマシンの能力

チューリングマシンは任意の文脈自由言語を判定できるだけでなく、プッシュダウン・オートマトンが判定できない言語（例えば素数の集合からなる言語）も判定可能である。したがってチューリングマシンはさらに強力な計算モデルと言うことができる。

チューリングマシンでは、入力テープに「バックアップ」を置くことができるため、上で説明した計算モデルには不可能な方法で動作可能である。入力に対して停止しないチューリングマシンを構築することもできる。チューリングマシンはあらゆる入力について停止して答え（言語と入力の判定）を返す機械である。