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

Weblio 辞書 > 固有名詞の種類 > 方式・規則 > 主義・方式 > 学問 > 学問 > 計算可能性理論の意味・解説 

計算可能性理論

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/11/11 17:50 UTC 版)

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

はじめに

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

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

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

計算の形式モデル

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

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

計算モデルの能力

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

有限状態機械の能力

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

正規言語でない言語の例として、文字 'a' と 'b' から構成され、各文字列に必ず 'a' と 'b' が同数含まれている言語がある。この言語が有限状態機械で認識できない理由を調べるため、まずこの言語を受容するための有限状態機械 概要英語版

  • カテゴリ
  • ブック
  • コモンズ

  • 計算可能性理論

    出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/09 06:43 UTC 版)

    計算理論」の記事における「計算可能性理論」の解説

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

    ※この「計算可能性理論」の解説は、「計算理論」の解説の一部です。
    「計算可能性理論」を含む「計算理論」の記事については、「計算理論」の概要を参照ください。

    ウィキペディア小見出し辞書の「計算可能性理論」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



    固有名詞の分類


    英和和英テキスト翻訳>> Weblio翻訳
    英語⇒日本語日本語⇒英語
      

    辞書ショートカット

    すべての辞書の索引

    「計算可能性理論」の関連用語











    計算可能性理論のお隣キーワード
    検索ランキング

       

    英語⇒日本語
    日本語⇒英語
       



    計算可能性理論のページの著作権
    Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

       
    ウィキペディアウィキペディア
    All text is available under the terms of the GNU Free Documentation License.
    この記事は、ウィキペディアの計算可能性理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
    ウィキペディアウィキペディア
    Text is available under GNU Free Documentation License (GFDL).
    Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの計算理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

    ©2025 GRAS Group, Inc.RSS