In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, an abstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is similar to a
mathematical function
In mathematics, a function from a set (mathematics), set to a set assigns to each element of exactly one element of .; the words ''map'', ''mapping'', ''transformation'', ''correspondence'', and ''operator'' are sometimes used synonymously. ...
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.
Abstract machines are "
machine
A machine is a physical system that uses power to apply forces and control movement to perform an action. The term is commonly applied to artificial devices, such as those employing engines or motors, but also to natural biological macromol ...
s" because they allow step-by-step execution of
programs; they are "
abstract" because they ignore many aspects of actual (
hardware) machines.
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.
In the
theory of computation, abstract machines are often used in
thought experiments
A thought experiment is an imaginary scenario that is meant to elucidate or test an argument or theory. It is often an experiment that would be hard, impossible, or unethical to actually perform. It can also be an abstract hypothetical that is ...
regarding
computability
Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is c ...
or to analyse the complexity of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s.
This use of abstract machines is fundamental to the field of
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, such as with
finite state machines,
Mealy machines,
push-down automata, and
Turing machines
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
.
Classification
Abstract machines are typically categorized into two types based on the quantity of operations they can execute simultaneously at any given moment:
deterministic abstract machines and
non-deterministic abstract machines.
A
deterministic
Determinism is the metaphysical view that all events within the universe (or multiverse) can occur only in one possible way. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping mo ...
abstract machine is a system in which a particular beginning state or condition always yields the same outputs. There is no randomness or variation in how inputs are transformed into outputs. In contrast, a
non-deterministic abstract machine can provide various outputs for the same input on different executions.
Unlike a deterministic algorithm, which gives the same result for the same input regardless of the number of iterations, a non-deterministic algorithm takes various paths to arrive to different outputs. Non-deterministic algorithms are helpful for obtaining approximate answers when deriving a precise solution using a deterministic approach is difficult or costly.
Turing machines
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
, for example, are some of the most fundamental abstract machines in computer science.
These machines conduct operations on a
tape (a string of symbols) of any length. Their instructions provide for both modifying the symbols and changing the symbol that the machine’s pointer is currently at. For example, a rudimentary Turing machine could have a single command, "convert symbol to 1 then move right", and this machine would only produce a string of 1s. This basic Turing machine is deterministic; however,
nondeterministic Turing machines that can execute several actions given the same input may also be built.
Implementation
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
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
. An abstract machine, however, can also be implemented in
software
Software consists of computer programs that instruct the Execution (computing), execution of a computer. Software also includes design documents and specifications.
The history of software is closely tied to the development of digital comput ...
or
firmware
In computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computer, computing machinery. It includes the study and experimentation of algorithmic processes, and the development of both computer hardware, h ...
at levels between the abstract machine and underlying physical device.
*
Implementation in hardware: The direct implementation of abstract machine in hardware is a matter of using physical devices such as
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembe ...
,
arithmetic
Arithmetic is an elementary branch of mathematics that deals with numerical operations like addition, subtraction, multiplication, and division. In a wider sense, it also includes exponentiation, extraction of roots, and taking logarithms.
...
and
logic circuits, buses, etc., to implement a physical machine whose machine language coincides with the
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
. Once constructed, it would be virtually hard to change such a machine.
A
CPU may be thought of as a concrete hardware realisation of an abstract machine, particularly the
processor's design.
*
Simulation using software: Implementing an abstract machine with software entails writing programmes in a different
language
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed language, signed forms, and may also be conveyed through writing syste ...
to implement the
data structures
In computer science, a data structure is a data organization and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functi ...
and
algorithms
In mathematics and computer science, an algorithm () is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...
needed by the abstract machine. This provides the most flexibility since programmes implementing abstract machine constructs can be easily changed.
An abstract machine implemented as a software simulation, or for which an
interpreter exists, is called a
virtual machine
In computing, a virtual machine (VM) is the virtualization or emulator, emulation of a computer system. Virtual machines are based on computer architectures and provide the functionality of a physical computer. Their implementations may involve ...
.
*
Emulation using firmware: Firmware implementation sits between hardware and software implementation. It consists of
microcode
In processor design, microcode serves as an intermediary layer situated between the central processing unit (CPU) hardware and the programmer-visible instruction set architecture of a computer. It consists of a set of hardware-level instructions ...
simulations of
data structures
In computer science, a data structure is a data organization and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functi ...
and
algorithms
In mathematics and computer science, an algorithm () is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...
for abstract machines.
Microcode
In processor design, microcode serves as an intermediary layer situated between the central processing unit (CPU) hardware and the programmer-visible instruction set architecture of a computer. It consists of a set of hardware-level instructions ...
allows a computer programmer to write machine
instructions without needing to fabricate
electrical circuitry.
Programming language implementation
An abstract machine is, intuitively, just an
abstraction
Abstraction is a process where general rules and concepts are derived from the use and classifying of specific examples, literal (reality, real or Abstract and concrete, concrete) signifiers, first principles, or other methods.
"An abstraction" ...
of the idea of a physical computer. For actual execution,
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s must be properly formalised using the constructs offered by a
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
. This implies that the algorithms to be executed must be expressed using programming language instructions.
The
syntax of a programming language enables the construction of
programs using a finite set of constructs known as instructions. Most abstract machines share
a program store and
a state, which often includes
a stack and registers.
In digital computers, the stack is simply a
memory unit with an address register that can count only positive integers (after an initial value is loaded into it). The address register for the stack is known as
a stack pointer because its value always refers to the top item on the stack. The program consists of a series of instructions, with
a stack pointer indicating the next instruction to be performed. When the instruction is completed,
a stack pointer is advanced. This fundamental control mechanism of an abstract machine is also known as its
execution loop.
Thus, an abstract machine for a programming language is any collection of
data structure
In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
s and algorithms capable of storing and running programs written in the programming language. It bridges the gap between the
high level of a programming language and the
low level of an actual machine by providing an intermediate language step for
compilation. An abstract machine's instructions are adapted to the unique operations necessary to implement operations of a certain source language or set of source languages.
Imperative languages
In the late 1950s, the
Association for Computing Machinery (ACM) and other allied organisations developed many proposals for
Universal Computer Oriented Language (UNCOL), such as
Conway's machine. The UNCOL concept is good, but it has not been widely used due to the poor performance of the generated
code
In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communicati ...
. In many areas of computing, its performance will continue to be an issue despite the development of the
Java Virtual Machine
A Java virtual machine (JVM) is a virtual machine that enables a computer to run Java programs as well as programs written in other languages that are also compiled to Java bytecode. The JVM is detailed by a specification that formally descr ...
in the late 1990s.
Algol Object Code (1964), P4-machine (1976),
UCSD P-machine (1977), and
Forth (1970) are some successful abstract machines of this kind.
Object-oriented languages
Abstract machines for
object-oriented programming languages
Object-oriented programming (OOP) is a programming paradigm based on the concept of '' objects''. Objects can contain data (called fields, attributes or properties) and have actions they can perform (called procedures or methods and impleme ...
are often
stack-based and have special access instructions for
object fields and
methods. In these machines,
memory management
Memory management (also dynamic memory management, dynamic storage allocation, or dynamic memory allocation) is a form of Resource management (computing), resource management applied to computer memory. The essential requirement of memory manag ...
is often implicit performed by a
garbage collector (memory recovery feature built into programming languages).
Smalltalk-80 (1980),
Self
In philosophy, the self is an individual's own being, knowledge, and values, and the relationship between these attributes.
The first-person perspective distinguishes selfhood from personal identity. Whereas "identity" is (literally) same ...
(1989), and
Java
Java is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...
(1994) are examples of this implementation.
String processing languages
A
string processing language is a computer language that focuses on processing strings rather than numbers. There have been string processing languages in the form of
command shells,
programming tools,
macro processors, and
scripting languages
In computing, a script is a relatively short and simple set of instructions that typically automation, automate an otherwise manual process. The act of writing a script is called scripting. A scripting language or script language is a programming ...
for decades. Using a suitable abstract machine has two benefits: increased
execution speed and enhanced portability.
Snobol4 and
ML/I are two notable instances of early string processing languages that use an abstract machine to gain machine independence.
Functional programming languages

The early abstract machines for
functional languages, including the
SECD machine (1964) and Cardelli's Functional Abstract Machine (1983), defined strict evaluation, also known as
eager or call-by-value evaluation,
in which function arguments are evaluated before the call and precisely once. Recently, the majority of research has been on
lazy (or call-by-need) evaluation, such as the G-machine (1984),
Krivine machine (1985), and Three Instruction Machine (1986), in which function arguments are evaluated only if necessary and at most once. One reason is because effective implementation of strict evaluation is now well-understood, therefore the necessity for an abstract machine has diminished.
Logical languages
Predicate calculus (first order logic) is the foundation of
logic programming languages
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure of ...
. The most well-known logic programming language is
Prolog
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics.
Prolog has its roots in first-order logic, a formal logic. Unlike many other programming language ...
. The rules in Prolog are written in a uniform format known as universally quantified 'Horn clauses', which means to begin the calculation that attempts to discover a proof of the objective. The
Warren Abstract Machine WAM (1983),
which has become the de facto standard in Prolog program compilation, has been the focus of most study. It provides special purpose instructions such as data unification instructions and control flow instructions to support backtracking (searching algorithm).
Structure
A generic abstract machine is made up of a
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembe ...
and an
interpreter. The memory is used to store data and programs, while the interpreter is the component that executes the instructions included in programs.

The interpreter must carry out the operations that are unique to the
language
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed language, signed forms, and may also be conveyed through writing syste ...
it is interpreting. However, given the variety of languages, it is conceivable to identify categories of operations and an "
execution mechanism" shared by all interpreters. The interpreter's operations and accompanying data structures are divided into the following categories:
# Operations for processing
primitive data:
# Operations and data structures for controlling the sequence of
execution of operations;
# Operations and data structures for controlling
data transfers;
# Operations and data structures for
memory management
Memory management (also dynamic memory management, dynamic storage allocation, or dynamic memory allocation) is a form of Resource management (computing), resource management applied to computer memory. The essential requirement of memory manag ...
.
Processing primitive data
An abstract machine must contain operations for manipulating primitive data types such as strings and integers.
For example, integers are nearly universally considered a basic data type for both physical abstract machines and the abstract machines used by many
programming languages
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their syntax (form) and semantics (meaning), usually defined by a formal language. Languages usually provide features ...
. The machine carries out the
arithmetic operations
Arithmetic is an elementary branch of mathematics that deals with numerical operations like addition, subtraction, multiplication, and Division (mathematics), division. In a wider sense, it also includes exponentiation, extraction of nth root, ...
necessary, such as addition and multiplication, within a single time step.
Sequence control
Operations and structures for "sequence control" allow controlling the
execution flow of program instructions. When certain
conditions are met, it is necessary to change the typical sequential execution of a program.
Therefore, the
interpreter employs data structures (such as those used to store the
address
An address is a collection of information, presented in a mostly fixed format, used to give the location of a building, apartment, or other structure or a plot of land, generally using border, political boundaries and street names as references, ...
of the next instruction to execute) that are modified by operations distinct from those used for data manipulation (for example, operations to update the address of the next instruction to execute).
Controlling data transfers
Data transfer operations are used to control how operands and data are transported from
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembe ...
to the interpreter and vice versa. These operations deal with the
store and the retrieval order of operands from the store.
Memory management
Memory management
Memory management (also dynamic memory management, dynamic storage allocation, or dynamic memory allocation) is a form of Resource management (computing), resource management applied to computer memory. The essential requirement of memory manag ...
is concerned with the operations performed in memory to allocate data and applications. In the abstract machine, data and programmes can be held indefinitely, or in the case of programming languages, memory can be allocated or deallocated using a more complex mechanism.
Hierarchies

Abstract machine hierarchies are often employed, in which each machine uses the functionality of the level immediately below and adds additional functionality of its own to meet the level immediately above. A
hardware computer, constructed with physical electronic devices, can be added at the most basic level. Above this level, the abstract
microprogrammed machine level may be introduced. The abstract machine supplied by the
operating system
An operating system (OS) is system software that manages computer hardware and software resources, and provides common daemon (computing), services for computer programs.
Time-sharing operating systems scheduler (computing), schedule tasks for ...
, which is implemented by a program written in
machine language
In computer programming, machine code is computer code consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). For conventional binary computers, machine code is the binaryOn nonb ...
, is located immediately above (or directly above the
hardware if the
firmware
In computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computer, computing machinery. It includes the study and experimentation of algorithmic processes, and the development of both computer hardware, h ...
level is not there). On the one hand, the operating system extends the capability of the physical machine by providing higher-level primitives that are not available on the physical machine (for example, primitives that act on files). The
host machine
A hypervisor, also known as a virtual machine monitor (VMM) or virtualizer, is a type of computer software, firmware or hardware that creates and runs virtual machines. A computer on which a hypervisor runs one or more virtual machines is called ...
is formed by the abstract machine given by the operating system, on which a
high-level programming language
A high-level programming language is a programming language with strong Abstraction (computer science), abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language ''elements'', be ea ...
is implemented using an
intermediary machine, such as the Java Virtual machine and its byte code language. The level given by the abstract machine for the
high-level language (for example, Java) is not usually the final level of hierarchy. At this point, one or more applications that deliver additional services together may be introduced. A "web machine" level, for example, can be added to implement the functionalities necessary to handle Web communications (
communications protocols or
HTML code presentation). The "
Web Service
A web service (WS) is either:
* a service offered by an electronic device to another electronic device, communicating with each other via the Internet, or
* a server running on a computer device, listening for requests at a particular port over a n ...
" level is located above this, and it provides the functionalities necessary to make web services communicate, both in terms of interaction protocols and the behaviour of the processes involved. At this level, entirely new languages that specify the behaviour of so-called "business processes" based on Web services may be developed (an example is the
Business Process Execution Language). Finally, a specialised application can be found at the highest level (for example,
E-commerce
E-commerce (electronic commerce) refers to commercial activities including the electronic buying or selling products and services which are conducted on online platforms or over the Internet. E-commerce draws on technologies such as mobile co ...
) which has very specific and limited functionality.
See also
*
*
*
*
*
*
* , the de facto standard model
*
*
References
Further reading
*Peter van Emde Boas, ''Machine Models and Simulations'' pp. 3–66, appearing in:
::
Jan van Leeuwen, ed. "Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity'', The MIT PRESS/Elsevier, 1990. (volume A). QA 76.H279 1990''
* Stephan Diehl, Pieter Hartel and Peter Sestoft
''Abstract Machines for Programming Language Implementation'' Future Generation Computer Systems, Vol. 16(7), Elsevier, 2000.
*
{{DEFAULTSORT:Abstract Machine
Automata (computation)
Models of computation