チューリング完全単語

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

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

概要

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

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

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

停止問題

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

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

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

関連項目

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

【スポンサーリンク】

  • 7
  • 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
記事編集 編集履歴を閲覧

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

お絵カキコがありません

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

ピコカキコがありません

チューリング完全

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が停止するならば暴走し、暴走するならば停止するプログラム」に、そのプログラム自身を入する
と書かなければならないのだが、これを分かりやすく記述することは私にはできそうにない
72 ななしのよっしん
2021/10/24(日) 04:14:41 ID: 3qW80C8kJc
ループ限処理状態を絶対検知して止める最強プログラムSTOP』くんがあるとする
最強なので、Trueを出して止めるまでループ処理する

じゃあSTOP』が子『STOP』を検知させたらどうなるの?
止まったら、子供ループ処理してないやん!ってなって矛盾
ループ処理してたら、が止めてないやん!ってなって矛盾
実は停止させる処理の大元、『STOP』くんの中身である検知機ガバってる
なので「”無限ループか止まるか検知するプログラム”は理じゃね?」っていう停止性問題

クレタ人は嘘つき、よってクレタ人はホモ Q.E.D 明終了
73 ななしのよっしん
2021/11/06(土) 20:13:43 ID: lDvZQCZSUN
>>72
あっ、そっかあ…
74 ななしのよっしん
2021/12/16(木) 13:52:45 ID: oei6aKjCTE
チューリング完全ってのは計算機科学の中でも計算理論、形式言って分野の話で
ここでいう計算ってのは一般的に思浮かべられる「計算の速さ」ではないっていうのはなかなか伝わらない
専門的には計算って言葉は使わなくて「言受理」と呼ぶ