情報科学 の チューリング完全に関する解説。

株式会社 日立ソリューションズ

HITACHI Inspire the Next

  • ホーム
  • ソリューション・商品
  • 事例紹介
  • セミナー・展示会
  • ビジネスコラム
  • 企業情報
  • お問い合わせ

チューリング完全

読み方、または別称:ちゅーりんぐかんぜん

計算理論で、ある計算のメカニズムがチューリング機械と同じ計算能力がある場合、その言語はチューリング完全(Turing-complete)、もしくは計算完備である。
例えばラムダ計算はチューリング完全であるが、これは、Yコンビネータでラムダ計算の範囲内で再帰することができ、ループと等価な能力を持つので証明される。同様に、μ再帰関数やマルコフアルゴリズムもチューリング完全である。
すなわち、プログラミング言語の多くはチューリング完全であり、一見単純な機能しか持たない言語がチューリング完全である例としては、純LISP、Lazy K、Brainfuckなどがある。ただし、正規表現はチューリング完全でなく、同様にSQLや、ループの書けない表計算マクロなどもチューリング完全ではない。
なお、計算理論(theory of computation)とは、計算模型やアルゴリズムを理論的に扱う学問で、計算複雑性理論や計算可能性理論を含む。また、チューリングマシン (Turing Machine) は数学的なの議論ための仮想機械である。

ページトップへ戻る

話題の用語

ITと社会用語辞典

ワークロード

ワークロードとは、システムのパフォーマンスを適正な状態に保つための指標のこと。

インターネット用語辞典

ライフログ

ライフログとは、人間の活動の記録(行動履歴)をデジタルデータとして記録すること、およびその記録のことである。

ページトップへ戻る

情報漏洩防止ソリューション 「秘文」

ITのお悩みをソリュっと解決! 特命課ソリュートくんがいく!

『オムニチャネル』から商品を探すページです。日立ソリューションズは、コンサルティングからシステム構築、サポートとトータルソリューションをご提供するシステムインテグレーション企業です。

ページトップへ戻る