現実の計算との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 20:23 UTC 版)
「チューリングマシン」の記事における「現実の計算との関係」の解説
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、算法あるいは算譜をチューリング機械と同一視する（チャーチ＝チューリングのテーゼ）。 数学の形式体系はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない（停止性問題）。これはゲーデルの不完全性定理の別の表現の形とみなすことができる。
※この「現実の計算との関係」の解説は、「チューリングマシン」の解説の一部です。
「現実の計算との関係」を含む「チューリングマシン」の記事については、「チューリングマシン」の概要を参照ください。
ウィキペディア小見出し辞書の「現実の計算との関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 現実の計算との関係のページへのリンク
