チューリング完全

チューリング完全とは、形式言語(プログラミング言語)が計算論的に能力カンストしている事をいう。

概要

簡単に言うと、チューリングマシンのエミュレータが(原理的に)書けるなら、その言語はチューリング完全である。逆にチューリングマシン上ではどんなプログラミング言語でも動かせるので、実効性能を問わなければCだろうがRubyだろうがBrainfuckだろうが「チューリング完全な言語間にできる／できないの優劣はない」というわけである。

なお、上では「原理的に」と濁しているが、チューリングマシンはメモリ無限大を仮定した理論上の機械なので完全なものは造れない。現実のコンピュータ（ノイマン型コンピュータと呼ばれる）は全てチューリングマシンのサブセットだが、「食べ放題」をうたうバイキングが誇大広告にならないようなもんだと思いねえ。

もっとも、およそプログラミング言語を名乗る程度の能力がある場合、チューリング完全でなくすほうが難しいぐらいなので大してレアな性能ではない。関連項目見れば言いたいことは分かってもらえると思う。

停止問題

「どんなチューリングマシンについても有限時間で停止するか暴走するかを判定できるチューリングマシンは設計できるか？」という問題。チューリングマシンをなんかしらのコンピュータプログラムと読み替えても同義。以下の証明では単に「プログラム」とする。

1. プログラムのソースコードを入力として、そのプログラムが正常に停止するかを判定できるプログラムAの存在を仮定する。
2. Aを利用して、あるプログラムが停止すると分かったら自身は暴走し、暴走すると分かったら自身は停止するプログラムBを作ることができる。
3. プログラムBにB自身を読み込ませてみる。
   1. Bが停止するならば、Bは暴走するはずだ。
   2. Bが暴走するならば、Bは停止するはずだ。
4. これらは明らかに矛盾している。故にプログラムAは存在しない。

ちなみにこれを数学的に書き換えるとゲーデルの第１不完全性定理になる。

関連項目

チューリング完全なものの一例。

• C言語
• Brainfuck
• ライフゲーム
• Minecraft
• スーパーマリオメーカー
• BABA IS YOU
• マジック:ザ・ギャザリング