「チューリングマシン」の版間の差分

(→‎厳密な定義: formal descriptionを形式的定義と訳していたので厳密な定義と修正。)
タグ: モバイル編集 モバイルウェブ編集
タグ: モバイルアプリ編集
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、[[アルゴリズム|算法]]あるいは[[算譜]]をチューリング機械と同一視する([[チャーチ=チューリングのテーゼ]])。
 
数学の[[形式体系]]はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない([[停止性問題]])。これは[[ゲーデルの不完全性定理]]の別表現の形とみなすことができる。
 
== 厳密な定義 ==
匿名利用者