計算可能性理論
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/11/11 17:50 UTC 版)
![]() |
この記事は、全部または一部が他の記事や節と重複しています。 具体的には再帰理論との重複です。 |
計算可能性理論(けいさんかのうせいりろん、英: computability theory)とは、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。
はじめに
理論計算機科学の中心的課題の1つとして、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処する、ということがあった。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし間違っており、そのことは「チューリングマシンの停止問題」の否定的解決として示された。以下では、そこに至る過程とそこから先の発展を述べる。
計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか?」である。この質問はやや難解なので、もう少し判り易く例を挙げる。まず、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。同様に、全ての回文の集合や、文字 'a' だけからなる全ての文字列の集合などが形式言語の例である。これらの例では、それぞれの問題を解くコンピュータの構築の容易さが言語によって異なることは明白である。
しかし、この観測された明白な違いはどういう意味で正確なのか? ある特定の問題をコンピュータで解く際の困難さの度合いを定式化し定義できるか? その質問に答えるのが計算可能性理論の目標である。
計算の形式モデル
計算可能性理論の中心課題に答えるために、「コンピュータとは何か」を形式的に定義する必要がある。利用可能な計算モデルはいくつか存在する。以下に代表例を挙げる。
- 決定性有限状態機械
- 決定性有限オートマトン(DFA)、あるいは単に有限状態機械とも呼ぶ。単純な計算モデルである。現在、実際に使われているコンピュータは、有限状態機械としてモデル化できる。この機械は状態の集合を持ち、入力列によって働く状態遷移の集合を持つ。一部の状態は受容状態と呼ばれる。入力列は一度に1文字ずつ機械に入力され、現在状態から状態遷移先への遷移条件と入力が比較され、マッチングするものがあればその状態が新たな状態となる。入力列が終了したとき機械が受容状態にあれば、全入力列が受容されたということができる。
- プッシュダウン・オートマトン
- 有限状態機械に似ているが、任意のサイズに成長可能な実行スタックを利用可能である点が異なる。状態遷移の際に記号をスタックに積むかスタックから記号を除くかを指定できる。
- チューリングマシン
- これも有限状態機械に似ているが、入力が「テープ」の形式になっていて、読むだけでなく書くこともでき、テープを送ったり巻き戻したりして読み書きの位置を決めることができる。テープのサイズは任意である。チューリングマシンは時間さえかければ、かなり複雑な問題も解くことができる。このモデルは計算機科学では最も重要な計算モデルであり、資源の限界がない計算をシミュレートしたものである。
計算モデルの能力
これらの計算モデルについて、その限界を定めることができる。すなわち、どのクラスの形式言語をその計算モデルは受容するか、である。
有限状態機械の能力
有限状態機械が受容する言語のクラスを正規言語と呼び、正規文法で記述される。有限状態機械が持つことができる状態は有限個であるためであり、正規言語でない言語を扱うには無限の状態数を扱える必要がある。
正規言語でない言語の例として、文字 'a' と 'b' から構成され、各文字列に必ず 'a' と 'b' が同数含まれている言語がある。この言語が有限状態機械で認識できない理由を調べるため、まずこの言語を受容するための有限状態機械 概要



計算可能性理論
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/09 06:43 UTC 版)
詳細は「計算可能性理論」を参照 計算可能性理論は、ある問題がコンピュータで解くことができるかどうかを扱う。チューリングマシンの停止問題は計算可能性理論における、ある意味で最も重要な成果である。定式化しやすく、かつチューリングマシンで解けない問題の具体例であり、数学基礎論との関係もある。同時に、静的に無限ループの検出を確実に行う方法は無いことを示している、といったように実応用的な意義もある。
※この「計算可能性理論」の解説は、「計算理論」の解説の一部です。
「計算可能性理論」を含む「計算理論」の記事については、「計算理論」の概要を参照ください。
固有名詞の分類
- 計算可能性理論のページへのリンク