Abstract machine

In computer science, an abstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions.^[1] It is similar to a mathematical function in that it receives inputs and produces outputs based on predefined rules. Abstract machines vary from literal machines in that they are expected to perform correctly and independently of hardware.^[2] Abstract machines are "machines" because they allow step-by-step execution of programmes; they are "abstract" because they ignore many aspects of actual (hardware) machines.^[3] 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. They can be used for purely theoretical reasons as well as models for real-world computer systems.^[2] In the theory of computation, abstract machines are often used in thought experiments regarding computability or to analyse the complexity of algorithms.^[3] This use of abstract machines is fundamental to the field of computational complexity theory, such as finite state machines, Mealy machines, push-down automata, and Turing machines.^[4]

Not to be confused with Virtual machine.

: The direct implementation of abstract machine in hardware is a matter of using physical devices such as memory, arithmetic and logic circuits, buses, etc., to implement a physical machine whose machine language coincides with the programming language. Once constructed, it would be virtually hard to change such a machine.^[9] A CPU may be thought of as a concrete hardware realisation of an abstract machine, particularly the processor's design.^[10]

Implementation in hardware

Any implementation of an abstract machine in the case of physical implementation (in hardware) uses some kind of physical device (mechanical or electronic) to execute the instructions of a programming language. An abstract machine, however, can also be implemented in software or firmware at levels between the abstract machine and underlying physical device.^[9]

– Approach to static program analysis

Abstract interpretation

– model for designing parallel algorithms

Bulk synchronous parallel

– Frameworks for modeling variables that evolve over time

Discrete time

– Classification of computer architectures

Flynn's taxonomy

– Ability to solve a problem in an effective manner

Formal models of computation

– Mathematical model describing how an output of a function is computed given an input

Model of computation

– Abstract computer for designing parallel algorithms, the de facto standard model

Parallel random-access machine

– Virtual and Abstract Machine target for functional programming language compiler

SECD machine

– Set of all possible values of a system

State space

Peter van Emde Boas, Machine Models and Simulations pp. 3–66, appearing in: