Abstract machine


Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. Abstraction of computing processes is used in both the computer science and computer engineering disciplines and usually assumes discrete time paradigm.

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 sets, registers 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

*ABC programming language
*Abstract Machine Notation
*ALF programming language
*Categorical Abstract Machine Language
*Context-free grammar
*Finite automata
*Specification and Design Language
* Historycal/Simplicity Abstract Machines for Prolog:
**1.Vienna Abstract Machine (VAM Prolog)
**2.Warren Abstract Machine (WAM Prolog)
**3.Berkeley Abstract Machine (BAM Prolog).
*MMIX
*TenDRA Distribution Format

ee also

*Abstraction (computer science)
*Discrete time
*State space
*Theory of computation#Other formal definitions of computation


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Abstract Machine Notation — (AMN) is a specification language and (abstract) programming language for specifying abstract machines in the B Method, based on the mathematical theory of Generalised Substitutions.Referencesee also* Formal methods * Formal specification …   Wikipedia

  • Warren Abstract Machine — Warren s Abstract Machine La Warren s Abstract Machine (Machine abstraite de Warren) est une machine virtuelle permettant d implémenter le langage Prolog. Cette machine est composée d un jeu d instructions spécial ainsi que d une mémoire. Elle a… …   Wikipédia en Français

  • Categorical abstract machine — (CAM) is the model of computation of a program [ Cousineau G., Curien P. L., Mauny M. The categorical abstract machine. LNCS, 201, Functional programming languages computer architecture. 1985, pp. 50 64.] , which preserves the abilities of… …   Wikipedia

  • Warren abstract machine — In 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set [War83] . This design became known as the Warren Abstract Machine (WAM) and has become the de facto… …   Wikipedia

  • Warren's Abstract Machine — La Warren s Abstract Machine (Machine abstraite de Warren) est une machine virtuelle permettant d implémenter le langage Prolog. Cette machine est composée d un jeu d instructions spécial ainsi que d une mémoire. Elle a été définie par David H. D …   Wikipédia en Français

  • Warren's Abstract Machine — Warren’s Abstract Machine (WAM) bezeichnet in der Informatik einen 1983 von David H. D. Warren spezifizierten idealen Prozessor, dessen Maschinensprache als Zielsprache für Prolog Übersetzer oder Interpreter dient. Man spricht auch von einer… …   Deutsch Wikipedia

  • Warren’s Abstract Machine — (WAM) bezeichnet in der Informatik einen 1983 von David H. D. Warren spezifizierten idealen Prozessor, dessen Maschinensprache als Zielsprache für Prolog Übersetzer oder Interpreter dient. Man spricht auch von einer virtuellen Maschine, da es den …   Deutsch Wikipedia

  • Machine (disambiguation) — Machine can refer to: * Machine, a device that performs a task * Rube Goldberg machine, an especially elaborate or complex device * abstract machine * Political machine, ex. Cook County Democratic Organization * The Machine, a muscle car made by… …   Wikipedia

  • Machine abstraite de Warren — Warren s Abstract Machine La Warren s Abstract Machine (Machine abstraite de Warren) est une machine virtuelle permettant d implémenter le langage Prolog. Cette machine est composée d un jeu d instructions spécial ainsi que d une mémoire. Elle a… …   Wikipédia en Français

  • Machine à différences — Machine analytique Reproduction moderne de la Machine analytique de Charles Babbage, fabriquée en 1992 pour le Musée des Sciences de Londres La machine analytique (analytical engine en anglais) est une machine de calcul inventée et créée en 1834… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.