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

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

  図 1: チューリング機械

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

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