通信用語の基礎知識 IPv4
戻る
参加者募集中

チューリングコンプリート

辞書:電算用語の基礎知識 計算機技術用語 (TCYOGO)
読み:チューリングコンプリート
外語:turing-complete 英語
品詞:形容動詞,名詞
2008/03/22 作成
2016/05/17 更新

プログラミング言語などにおいて、それがチューリングマシンと同じ能力を持っていること。チューリング完全。

一般に、プログラミング言語と称されるものは、ほぼ全てがチューリングコンプリートである。

単純そうに見えても、能力を満たす言語としては、BrainfuckWhitespaceGrassなどといったものがある。

現在使われている主流のプログラミング言語は、このような単純な言語に、更に使いやすさを加えたものである、ともいえる。

条件

チューリングマシンと同じ能力を持てばよい。最低限、次の機能を持っていれば、それは、記述性や可読性に問題があったとしても、チューリングコンプリートとなる。

  • ポインターを前後に移動できる
  • ポインター位置の情報を読み取ることができる
  • ポインター位置に情報を書き込むことができる
  • 読み取った情報またはポインター位置の情報を変更することができる

つまり「読んで」「書いて」「比較できて」「条件ジャンプまたはプログラムのループができる」ことが少なくとも必要であると言える。

この他、実用面においては、結果を画面に出す機能なども必要だろう。

そしてこれだけの機能が備わっていることから、BrainfuckWhitespaceなどは、明らかに実用的ではないがチューリングコンプリートと言える。

除外

次のようなものは、チューリングコンプリートではない。

SQLはチューリングコンプリートではないが、OracleがSQLをプログラミング言語に改造したPL/SQLはチューリングコンプリートである。

TeX

マークアップ言語であり版組エンジンであるTeXは、プログラムを書くことができる。

作者のKnuthは、TeXをプログラミング言語にするつもりはなかったと思われるが、版組に必要な機能を詰め込んだ結果、最終的に「チューリングコンプリートの関数型言語」になってしまったという、非常に稀な例である。

ラムダ計算

数式ではあるが、λ計算(ラムダ計算)はチューリングコンプリートである。

数式にループの機能など存在し得ないが、しかしλ計算は不動点コンビネータ(Yコンビネータ)で再帰を定義することが可能であり、これが事実上ループと等価の効果をもたらすため、λ計算はチューリングコンプリートなのである。

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.03 (16-May-2019)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club