> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/600-toc/610-automata-theory/abstract-machine.md). # Abstract machine An abstract machine is a *theoretical computer* used for defining a *model of computation*. Abstract machines are *machines* because they permit step-by-step execution of programs; they are *abstract* because they omit many details of real hardware machines. Abstraction of computing processes is used in both the computer science and computer engineering disciplines and usually assumes a discrete time paradigm. In theory of computation, abstract machines are often used in thought experiments regarding computability or to analyze the complexity of algorithms. A typical abstract machine is defined in terms of input, output, and the set of operations that turn input into output. The best-known example of an abstract machine is the Turing machine. *Abstract data types* (ADT) can be specified in terms of their operational semantics on an abstract machine. For example, a stack can be specified in terms of operations on an abstract machine with an array of memory. 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 a physical system. Turing machine Decider Linear-bounded PTIME Turing Machine Nested stack Thread automaton restricted Tree stack automaton Embedded pushdown Nondeterministic pushdown Deterministic pushdown Visibly pushdown Finite Counter-free (with aperiodic finite monoid) Acyclic finite A **stack machine** type of computer (as opposed to a stack emulation in software) operates using a *push-down automata*. Stack is a simple structure for storing and retrieving data since with a rigid LIFO discipline (only the topmost item is accessable), which is the reason this types of machines use prefix notation with operator followed by operands. A **register machine** has a flexible storage scheme; each instruction explicitly addresses specific registers which can be used to store and load operands. A more complex definition of an abstract machines includes full instruction set, registers and models of memory. A popular model, similar to real machines, is the **RAM model**, which allows random access to indexed memory locations. A **virtual machine** is a abstract machine implemented in software which has an interpreter.