Product Design, Manufacturing & Innovation Resources
» チューリング完全性

チューリング完全性

1936
  • Alan Turing
Computer science lab showcasing Turing completeness in programming languages.

(画像はイメージです)

データ操作ルールのシステム、例えば プログラミング言語チューリング完全とは、あらゆる単一テープのチューリングマシンをシミュレートできることを意味します。つまり、十分な時間とメモリがあれば、計算可能なあらゆる問題を解決するために使用できる、計算的に普遍的なシステムであるということです。ほとんどの汎用プログラミング言語はチューリング完全であり、それが表現力の理論的基盤となっています。

チューリング完全性とは、計算可能性理論における概念であり、計算システムの能力を定義するものです。これは、アラン・チューリングが1936年に発表した、チューリングマシンと呼ばれる理論的な装置を記述した論文に由来します。このマシンは、無限に長いテープ、テープに沿って読み書きおよび移動できるヘッド、そして一連の状態と遷移規則から構成されます。その単純さにもかかわらず、チューリングマシンはアルゴリズム的に記述できるあらゆる計算を実行できます。プログラミング言語やその他の形式体系は、汎用チューリングマシンをシミュレートできる能力があれば、「チューリング完全」であるとみなされます。これは、その言語が計算可能なあらゆるものを計算できることを意味します。

システムがチューリング完全であるための基本的な要件は、条件分岐(if-then-else文など)と無限ループまたは再帰ループ(whileループ、forループなど)を実行できる機能です。これらの構成要素により、システムは意思決定を行い、操作を繰り返すことができ、チューリングマシンの状態遷移やテープ操作の動作をモデル化するのに十分です。コンピュータ科学の基本原理であるチャーチ=チューリングのテーゼは、自然に「計算可能」と考えられる関数はすべてチューリングマシンで計算できると提唱しています。したがって、理論的には、チューリング完全な言語はあらゆるアルゴリズムを表現できることになります。

しかし、この理論的な力には重大な結果が伴います。それは停止問題です。チューリングは、あらゆる入力に対して、任意のプログラムが実行を終了するか、あるいは無限ループに陥るかを判定できる汎用アルゴリズムを作成することは不可能であることを証明しました。この決定不可能性は、すべてのチューリング完全システムに固有の性質です。そのため、一部のドメイン固有言語は意図的にチューリング完全ではないように設計されています。例えば、標準SQLやHTMLはチューリング完全ではないため、スクリプトや定義が必ず終了し、意図せず無限ループに陥ることを防ぎます。これは、データベースクエリやドキュメントレンダリングにおいて望ましい特性です。

UNESCO Nomenclature: 1202
コンピュータサイエンス

タイプ

抽象システム

混乱

増分

使用法

広く普及している

前駆物質

  • Kurt Gödel’s work on incompleteness theorems
  • アロンゾ・チャーチによるラムダ計算の開発
  • デイヴィッド・ヒルベルトによる数学の形式化プログラム
  • アルゴリズムの概念は古代にまで遡る

アプリケーション

  • 汎用プログラミング言語(Python、C++、Java)
  • マクロ機能を備えた表計算システム(例:VBAを搭載したExcel)
  • マインクラフトのレッドストーン回路
  • cellular automata like conway’s game of life
  • 再帰的な共通テーブル式を用いた高度なSQL拡張機能
  • C++テンプレートメタプログラミングサブシステム
  • 特定のHTMLの組み合わせによるCSS3

特許:

NA

潜在的なイノベーションのアイデア

ボットによるトラフィック(現在1日あたり4万件以上)を排除するため、このコンテンツはコミュニティメンバー限定となっています。
> ログイン < または > 登録 < (100%無料)でこれにアクセスできます。他のすべての制限付きコンテンツとツールも同様です。

関連キーワード:チューリング完全性、チューリングマシン、計算可能性理論、アラン・チューリング、チャーチ=チューリングのテーゼ、普遍計算、アルゴリズム、形式言語、決定可能性、停止問題。

歴史的背景

チューリング完全性

1925
1928
1930
1936
1940
1943
1950
1924
1925
1930
1931
1939
1940
1950
1950

(日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。)

関連する発明、革新、および技術原理

フルサイズの画像とダウンロードは、登録会員のみが100%無料で利用できます。