ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


チューリング完全


ヨミ: ケイサンカンビ
掲示板をミル!
71カキコ!

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


概要


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

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

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


停止問題


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

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

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


関連項目


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


最終更新日: 20/08/02 23:36
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ