通信用語の基礎知識 全国のICカードこれひとつ 戻る

通常PC用 / 人気 更新 今日 カテ
電子計算機 > 理論
電子計算機 > 仕様・構造 > ソフトウェア > プログラミング言語 > 言語仕様
チューリングコンプリート
辞書:電算用語の基礎知識 計算機技術用語 (TCYOGO)
読み:チューリングコンプリート
外語:turing-complete
品詞:形容動詞,名詞

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

目次
概要

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

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

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

特徴
条件

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

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

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

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

除外

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

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

TeX

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

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

ラムダ計算

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

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

リンク
用語の所属
チューリングマシン
プログラミング言語

[再検索] [戻る]


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