チューリングマシン チューリングマシンの概要

チューリングマシン

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/03/29 08:54 UTC 版)

ナビゲーションに移動 検索に移動

歴史

チューリングの「計算可能数について──決定問題への応用」(1936年)において提示された。同様なものを同年にエミール・ポスト (Emil Post) も独立に発表している。構想の理由、動機についてはポストの論文が明確だが、機械自体に関する記述はチューリングの論文が詳細である。次いで、同時代に提示された他の計算モデル計算可能性の理論からは同等であることが確認され、チューリング=チャーチのテーゼはそれらを「計算可能」の定義とすることを提唱した。

概要

ここでは非形式的(直感的)に述べる。理論的には形式的に述べる必要がある。

チューリングマシンには、いわゆるハードウェアに相当するものとして、

  1. その表面に記号を読み書きできるテープ。長さは無制限(必要になれば順番にいくらでも先にシークできる[注 1])とする
  2. (テープに記号を読み書きするヘッド)
  3. ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトン

がある。

また、ソフトウェアに相当するものとして、以下がある。

  1. テープに読み書きされる有限個の種類の記号
  2. 最初から(初期状態において)テープにあらかじめ書かれている記号列
  3. 有限オートマトンの状態遷移規則群。詳細は次で述べる

この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」(内部状態)と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。

  • テープの「現在の場所」に新しい記号を書き込む(あるいは、現在の記号をそのままにしてもよい)
  • ヘッドを右か左に一つシークする(あるいは、移動しなくてもよい)
  • 有限オートマトンを次の状態に状態遷移させる(同じ状態に遷移してもよい)

さらに、この有限オートマトンには(一般的な有限オートマトンの「受理状態」と同様な)「受理状態」がある。計算可能性理論的には、決定問題の2種類の答えに対応する、2種類の受理状態が必要である[注 2]

現実の計算との関係

実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、算法あるいは算譜をチューリング機械と同一視する(チャーチ=チューリングのテーゼ)。

数学の形式体系はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない(停止性問題)。これはゲーデルの不完全性定理の別の表現の形とみなすことができる。


  1. ^ 一般的には両方向にいくらでもシークできるものとするが、理論的には片方には端があっても良いのでそのように制限することもある。
  2. ^ あるいは単に停止する場合は、停止する前に、答えがどちらであるかを、テープ上の記号列として書き残してから停止する。


「チューリングマシン」の続きの解説一覧



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「チューリングマシン」の関連用語

チューリングマシンのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



チューリングマシンのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのチューリングマシン (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2021 GRAS Group, Inc.RSS