Abstract machine
Encyclopedia
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 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.
abstract machines. This taxonomy does not include finite automata:
Family: Turing-equivalent (TE) abstract machine:
Subfamilies:
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: This includes the following "species":
Genus (1.2)-- The register machine model: This includes (at least) the following four "species" (others are mentioned by van Emde Boas):
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
hardware or software system used in automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
. Abstraction of computing processes is used in both the computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and computer engineering
Computer engineering
Computer engineering, also called computer systems engineering, is a discipline that integrates several fields of electrical engineering and computer science required to develop computer systems. Computer engineers usually have training in electronic engineering, software design, and...
disciplines and usually assumes discrete time
Discrete time
Discrete time is the discontinuity of a function's time domain that results from sampling a variable at a finite interval. For example, consider a newspaper that reports the price of crude oil once every day at 6:00AM. The newspaper is described as sampling the cost at a frequency of once per 24...
paradigm
Paradigm
The word paradigm has been used in science to describe distinct concepts. It comes from Greek "παράδειγμα" , "pattern, example, sample" from the verb "παραδείκνυμι" , "exhibit, represent, expose" and that from "παρά" , "beside, beyond" + "δείκνυμι" , "to show, to point out".The original Greek...
.
In the theory of computation
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
, abstract machines are often used in thought experiments regarding computability or to analyze the complexity of algorithms (see computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
). 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
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
.
More complex definitions create abstract machines with full instruction set
Instruction set
An instruction set, or instruction set architecture , is the part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O...
s, register
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
s and models of memory
Memory hierarchy
The term memory hierarchy is used in the theory of computation when discussing performance issues in computer architectural design, algorithm predictions, and the lower level programming constructs such as involving locality of reference. A 'memory hierarchy' in computer storage distinguishes each...
. One popular model more similar to real modern machines is the RAM model, which allows random access
Random access
In computer science, random access is the ability to access an element at an arbitrary position in a sequence in equal time, independent of sequence size. The position is arbitrary in the sense that it is unpredictable, thus the use of the term "random" in "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
Cache-oblivious model
In computing, a cache-oblivious algorithm is an algorithm designed to take advantage of a CPU cache without having the size of the cache as an explicit parameter...
are growing in importance.
An abstract machine can also refer to a microprocessor
Microprocessor
A microprocessor incorporates the functions of a computer's central processing unit on a single integrated circuit, or at most a few integrated circuits. It is a multipurpose, programmable device that accepts digital data as input, processes it according to instructions stored in its memory, and...
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
Interpreter (computing)
In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language...
exists, is called a virtual machine
Virtual machine
A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...
.
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 equivalentTuring completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...
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 machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
model
- Genus (1.2) Register-based register machineRegister machineIn mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing 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 machineNon-deterministic Turing machineIn theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
, Wang B-machineWang B-machineAs presented by Hao Wang , his basic machine B is an extremely simple computational model equivalent to the Turing machine. It is "the first formulation of a Turing-machine theory in terms of computer-like models" . With only 4 sequential instructions it is very similar to, but even simpler than,...
, Post-Turing machinePost-Turing machineA Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below. A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a...
, Oracle machineOracle machineIn complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
, Universal Turing machineUniversal Turing machineIn computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
}
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 machineCounter machineA counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines...
, (1.2.2) Random access machineRandom access machineIn computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
RAM, (1.2.3) Random access stored program machineRandom access stored program machineIn theoretical computer science the Random Access Stored Program machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory....
RASP, (1.2.4) Pointer machinePointer machineIn theoretical computer science a pointer machine is an "atomistic" abstract computational machine model akin to the Random access 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 architectureHarvard architectureThe Harvard architecture is a computer architecture with physically separate storage and signal pathways for instructions and data. The term originated from the Harvard Mark I relay-based computer, which stored instructions on punched tape and data in electro-mechanical counters...
; any model with an "accumulator" with additional indirect addressing but instructions in the state machine in the Harvard architecture }
- { any counter-machine model with additional indirect addressing, but with 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 architectureVon Neumann architectureThe term Von Neumann architecture, aka the Von Neumann model, derives from a computer architecture proposal by the mathematician and early computer scientist John von Neumann and others, dated June 30, 1945, entitled First Draft of a Report on the EDVAC...
}
- { 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 languageABC programming languageABC is an imperative general-purpose programming language and programming environment developed at CWI, Netherlands by Leo Geurts, Lambert Meertens, and Steven Pemberton. It is interactive, structured, high-level, and intended to be used instead of BASIC, Pascal, or AWK...
- Abstract Machine NotationAbstract Machine NotationThe abstract machine notation is a specification language and programming language for specifying abstract machines in the B method, based on the mathematical theory of generalised substitutions....
- Algebraic Logic Functional programming languageAlgebraic Logic Functional programming languageAlgebraic Logic Functional programming language also known as ALF is a programming language which combines functional and logic programming techniques...
- Categorical Abstract Machine Language
- Context-free grammarContext-free grammarIn formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
- Finite automata
- Specification and Design Language
- Historycal/Simplicity Abstract Machines for PrologPrologProlog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
:- 1.Vienna Abstract Machine (VAM Prolog)
- 2.Warren Abstract MachineWarren abstract machineIn 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set. This design became known as the Warren Abstract Machine and has become the de facto standard target for Prolog compilers.-Purpose:The purpose of...
(WAM Prolog) - 3.Berkeley Abstract Machine (BAM Prolog).
- MMIXMMIXMMIX is a 64-bit RISC instruction set architecture designed by Donald Knuth, with significant contributions by John L. Hennessy and Richard L. Sites...
- MikroSimMikroSimThe program MikroSim is an educational software for hardware-non-specific explanation of the general functioning and behaviour of a virtual processor, running on the operating system Microsoft Windows...
- SECD abstract machine
- Ten15Ten15Ten15 is an algebraically specified abstract machine. It was developed by Foster, Currie et al. at the Royal Signals and Radar Establishment at Malvern, Worcestershire, during the 1980s. It arose from earlier work on the Flex machine, which was a capability computer implemented via microcode...
- TenDRA Distribution FormatTenDRA Distribution FormatThe abstract machine TDF evolved at the Royal Signals and Radar Establishment in the UK as a successor to Ten15. Its design allowed support for the C programming language...
- Zinc abstract machine
See also
- Abstraction (computer science)Abstraction (computer science)In computer science, abstraction is the process by which data and programs are defined with a representation similar to its pictorial meaning as rooted in the more complex realm of human life and language with their higher need of summarization and categorization , while hiding away the...
- Abstract interpretationAbstract interpretationIn computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer program which gains information about its semantics In...
- Discrete timeDiscrete timeDiscrete time is the discontinuity of a function's time domain that results from sampling a variable at a finite interval. For example, consider a newspaper that reports the price of crude oil once every day at 6:00AM. The newspaper is described as sampling the cost at a frequency of once per 24...
- State spaceState spaceIn the theory of discrete dynamical systems, a state space is a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from a to b if and only if ƒ = b where the function f defines the dynamical system.State spaces are...
- Computability#Formal models of computation