チューリング完全 【Turing complete】 計算完備

概要

チューリング完全（Turing complete）とは、何らかの計算を行う機構(論理回路や人工言語とその処理系など)が、万能チューリングマシンに等しい能力を持っていること。あらゆる計算を記述、実行できることを表す。

チューリングマシンは1936年にイギリスの数学者アラン・チューリング（Alan M. Turing）が考案した計算機械の数学的なモデルで、形式的な記号操作の組み合わせ、繰り返しで構成されるすべての計算を実行することができる、

チューリングマシンの構成や動作は符号列として定義および記述することが可能だが、任意の符号化されたチューリングマシンを受け取って、その動作を完全に真似ることができるチューリングマシンを「万能チューリングマシン」（universal Turing machine）という。

汎用のソフトウェア開発を念頭に開発されているマイクロプロセッサ（CPU/MPU）やほとんどのプログラミング言語はチューリング完全だが、組版言語のTeXやC言語のプリプロセッサなど、プログラミングを主用途としない言語などでも（開発者が意図せず）チューリング完全になっているものがある。

あくまで理論上は万能チューリングマシンを構成可能であるという意味であり、効率性や可読性は考慮されない。極限まで言語仕様を縮小した数語程度しか命令語を持たない難解なプログラミング言語（ほとんど実用にはならない）や、極めて単純な論理回路などでもチューリング完全となりうることが知られている。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。