ニコニコ大百科モバイル

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


チューリング完全


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

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


概要


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

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

計算論だ、停止問題だ、不完全性定理だといった厳密な話はググれ

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


最終更新日: 11/02/08 01:13
タグ検索 パソコン版を見る


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