Abstract Machine - Articles Concerning Turing-equivalent Sequential Abstract Machine Models

Articles Concerning Turing-equivalent Sequential Abstract Machine Models

An approach is to take a somewhat formal taxonomic approach to classify the Turing equivalent abstract machines. This taxonomy does not include finite automata:

Family: Turing-equivalent (TE) abstract machine:

Subfamilies:

Subfamily (1) Sequential TE abstract machine

Subfamily (2) Parallel TE abstract machine

Subfamily (1)-- Sequential TE abstract machine model: There are two classes (genera) of Sequential TE abstract machine models currently in use (cf van Emde Boas, for example):

Genus (1.1) Tape-based Turing machine model

Genus (1.2) Register-based register machine

Genus (1.1) -- Tape-based Turing machine model: This includes the following "species":

{ single tape, Multi-tape Turing machine, deterministic Turing machine, Non-deterministic Turing machine, Wang B-machine, Post-Turing machine, Oracle machine, Universal Turing machine }

Genus (1.2)-- The register machine model: This includes (at least) the following four "species" (others are mentioned by van Emde Boas):

{ (1.2.1) Counter machine, (1.2.2) Random access machine RAM, (1.2.3) Random access stored program machine RASP, (1.2.4) Pointer machine }

Species (1.2.1) -- Counter machine model:

{ abacus machine, Lambek machine, Melzak model, Minsky machine, Shepherdson-Sturgis machine, program machine, etc. }

Species (1.2.2) -- Random access machine (RAM) model:

{ any counter-machine model with additional indirect addressing, but with instructions in the state machine in the Harvard architecture; any model with an "accumulator" with additional indirect addressing but instructions in the state machine in the Harvard architecture }

Species (1.2.3) -- Random access stored program machine (RASP) model includes

{ any RAM with program stored in the registers similar to the Universal Turing machine i.e. in the von Neumann architecture }

Species (1.2.4)-- Pointer machine model includes the following:

= { Schönhage Storage Modification Machine SMM, Kolmogorov-Uspensky KU-machine, Knuth linking automaton }