Information AboutAbstract Machine |
| CATEGORIES ABOUT ABSTRACT MACHINE | |
| discrete mathematics | |
| theory of computation | |
|
In the Theory Of Computation , abstract machines are often used in Thought Experiments regarding computability or to analyze the complexity of algorithms (''see'' Computational Complexity Theory ). A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former into the latter. The best-known example is the Turing Machine . More complex definitions create abstract machines with full Instruction Set s, Register s and models of Memory . One popular model more similar to real modern machines is the RAM Model , which allows random access to indexed memory locations. As the performance difference between different levels of cache memory grows, cache-sensitive models such as the External-memory Model and Cache-oblivious Model are growing in importance. An abstract machine can also refer to a Microprocessor design which has yet to be (or is not intended to be) implemented as hardware. An abstract machine implemented as a software simulation, or for which an Interpreter exists, is called a Virtual Machine . Through the use of abstract machines it is possible to compute the amount of resources (time, memory, etc.) necessary to perform a particular operation without having to construct an actual system to do it. 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 } OTHER ABSTRACT MACHINES
SEE ALSO
] |
|
|