チューリング完全単語

ケイサンカンビ
  • 6
  • 0pt
掲示板へ

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

概要

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

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

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

停止問題

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

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

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

関連項目

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

【スポンサーリンク】

  • 6
  • 0pt
スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E5%AE%8C%E5%85%A8

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

チューリング完全

62 ななしのよっしん
2019/09/06(金) 03:27:41 ID: 9F4SJMdR/H
宇宙チューニング全だと思うぞ
現にコンピューター再現できているからな
63 ななしのよっしん
2019/11/25(月) 21:26:26 ID: +ObWcAYyfz
人間チューリング完全
コンピューターで解けない問題は人間でも解けない?
64 ななしのよっしん
2019/11/25(月) 21:48:43 ID: R68CisMbb5
↑そう考えている研究者もいる。一方でチューリングマシンえうる可性を持つ仮説上のモデル機械」としてをとらえようとする考えもある。
65 ななしのよっしん
2019/12/14(土) 23:31:31 ID: lLE6l/nK/r
チューリング完全かどうかってのは、審判ルール)が信用できるかどうかってことだと考えれば理解しやすい
審判の気分次第で裁定が変わっちゃったり、やる気くして職務放棄するようなものはチューリング完全では
66 ななしのよっしん
2019/12/14(土) 23:37:47 ID: 3uy1H/ufYH
チューリング完全であることに意味があるものでもない限り、チューリング完全ですとか言われてもだからどうしたと思ってしまう。
67 削除しました
削除しました ID: GBzbWymJoD
削除しました
68 ななしのよっしん
2020/06/08(月) 18:55:09 ID: azaqMJ9pRv
BABA IS YOUチューリング完全だったんだ...
69 ななしのよっしん
2020/12/04(金) 19:26:17 ID: Y9+EC7BwYJ
現実コンピュータノイマンコンピュータイコールではない。ほとんどがノイマンなだけで、非ノイマンでもコンピュータは作れる。そこはついちゃダメ。
70 ななしのよっしん
2020/12/04(金) 20:59:22 ID: R68CisMbb5
ちなみにインテルCPUの内部は命データが分離した「ハーバード・アーキテクチャ」と言う非ノイマン構造だ。
71 ななしのよっしん
2021/01/04(月) 14:12:32 ID: aiNzcTVO5O
「Aを利用して、あるプログラムが停止すると分かったら自身は暴走し、暴走すると分かったら自身は停止するプログラムBを作ることができる。」という表現では、入されるデータによって停止したり暴走したりするプログラムにBがどう反応するか述べられていないから矛盾を導けない。
「Xを入すると、プログラムXにX自身を入したときにXが停止するならば暴走し、暴走するならば停止するプログラム」に、そのプログラム自身を入する
と書かなければならないのだが、これを分かりやすく記述することは私にはできそうにない

急上昇ワード改

過去のオススメ記事