抽象機械 階層的分類

ウィキペディア

抽象機械

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/08/25 15:49 UTC 版)

階層的分類

いくらかの抽象機械は、階層的に分類できる。ここではチューリング完全のもののみを対象とする。以下は網羅したものではないし、このような分類のしかたが唯一のものというわけでもない。

• 直列計算の機械
• 並列計算の機械

以下は直列計算の機械のみである。

• テープベース - チューリングマシンの変形など
  • シングルテープ、マルチテープチューリングマシン、決定的チューリングマシン、非決定的チューリングマシン、Wang B-マシン、ポストチューリングマシン、神託機械、万能チューリングマシン
• レジスタベース - レジスタマシン
  • counter machine、RAM（Random-Access Machine）、RASP（Random-Access Stored-Program machine）、pointer machine

レジスタベースのそれぞれについての詳細は以下のようになる。

• counter machine
  • （en:Counter machine も参照）アバカスマシン、Lambekマシン、Melzakモデル、ミンスキーマシン、Shepherdson-Sturgisマシン、プログラムマシン
• RAM（Random-Access Machine）
  • （en:Random-access machine を参照）
• RASP（Random-Access Stored-Program machine）
  • （en:Random-access stored-program machine も参照）ノイマンマシン
• pointer machine
  • （en:Pointer machine も参照）Schonhage Storage Modification Machine SMM, Kolmogorov-Uspensky KU-machine, Knuth linking automaton