Abstract machines are theoretical computer science elements that receive inputs and produce outputs according to specified rules. They work perfectly and independently of hardware and are classified based on their operations and input types. Examples include Conway’s Game of Life and the Turing machine, which can serve as models for real computer systems.
Abstract machines, also called automata, are an element of theoretical computer science. An abstract machine looks like a function in mathematics. It receives inputs and produces outputs according to specified rules. Abstract machines differ from more literal machines in that they are assumed to work perfectly and independently of hardware. They are divided into types based on characteristics such as how they carry out their operations and what types of inputs they can receive.
When classifying abstract machines, one of the simplest distinctions involves the number of operations they can perform at any given point. An abstract machine is said to be deterministic if there is always only one way to proceed. It is not deterministic if there are multiple possibilities for the machine in at least one of its possible states. A “pushdown” automaton is one that has the ability to manipulate its stack of inputs, rather than simply responding to them one by one in the order they appear.
Wolfram MathWorld provides two famous examples of abstract machines. One such example is Conway’s Game of Life, which is a deterministic abstract machine because only one configuration can emerge from any other. This game uses a grid where each square, or cell, can have the status “alive” or “dead”. The status of the entire network is determined based on the previous status. If a living cell touches exactly two or three other living cells, it continues to live. If it has one, two, or more than three neighbors (up to a possible eight), it dies. A dead cell with exactly three neighbors will come to life; otherwise, it will remain dead.
Another example, the Turing machine, is one of the most basic and fundamental abstract machines in computing. A Turing machine performs operations on a tape, a string of symbols, of unlimited size. Contains instructions for both changing symbols and changing the symbol it is operating on. A simple Turing machine might just have the statement “turn the symbol to 1, then move right.” This machine would produce nothing but a string of 1s. This simple Turing machine is deterministic, but it is also possible to build nondeterministic Turing machines that can perform different operations given the same input.
These abstract machines can serve many purposes. They can be fun theory toys, but they can also serve as models for real computer systems. The abstract machine is at the heart of computer science as a discipline.
Protect your devices with Threat Protection by NordVPN
