2 チューリング機械とノイマン型コンピューター

• チューリング機械は，図1のような構造をし ています．そして，その動作は，次の通りです．
  • 書き換え可能な無限に長いテープと，オートマトンと言われる移動可能な 機械からできている．
  • テープには，いろいろな記号が書かれている．
  • オートマトンには，テープの内容を読み書き可能なヘッドと内部状態を記 憶する装置，テープの任意の位置に移動する装置から構成されている．
  • オートマトンの動作(テープの読み書き)や移動は，今の場所のテープの記 号と内部状態により決まる．

  図 1: チューリング機械

  
• この単純なチューリング機械で，ほとんどあらゆる計算ができます．計算できな い問題もあるようですが，これはここの講義のレベルを超えます．
• このチューリング機械を実際に実現させたものが，ノイマン型コンピューターで す．その特徴は，以下の通りです．
  • 1次元的に並んだメモリーがあり，そこにプログラム(命令)もデータも格納 される．メモリーの内容は，自然数の番地で参照できる．
  • メモリーに格納されたプログラム(命令)とデータの見かけ上の区別はない． プログラムをデータとして見ることも，データをプログラムとしてみるこ ともできる．

ホームページ: Yamamoto's laboratory
著者: 山本昌志