Category: 

What is an Abstract Machine?

Article Details
  • Written By: Leo Zimmermann
  • Edited By: Kathryn Hulick
  • Last Modified Date: 20 November 2016
  • Copyright Protected:
    2003-2016
    Conjecture Corporation
  • Print this Article
Free Widgets for your Site/Blog
NASA scientists have discovered a class of stars with atmospheric temperatures cooler than the human body.  more...

December 2 ,  1982 :  The first permanent artificial heart was implanted in a human.  more...

Abstract machines, also called automata, are an element of theoretical computer science. An abstract machine resembles a function in mathematics. It receives inputs and produces outputs according to specified rules. Abstract machines differ from more literal machines because they are assumed to function perfectly and independently from hardware. They are subdivided into types on the basis of characteristics such as how they perform their operations and what types of inputs they can receive.

When classifying abstract machines, one of the most simple distinctions concerns the number of operations they are permitted to perform at any given point. An abstract machine is called deterministic if there is always only one way for it to proceed. It is nondeterministic if multiple possibilities exist for the machine in at least one of its possible states. A "pushdown" automaton is one that has the capacity to manipulate its stack of inputs, rather than simply responding to them one by one in the order in which they appear.

Ad

Wolfram MathWorld gives two famous examples of abstract machines. One of these examples is Conway's game of life, which is a deterministic abstract machine because only one configuration can emerge out of any other. This game uses a grid in which each box, or cell, can either have the state "living" or "dead." The state of the whole grid is determined on the basis of the previous state. 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 computer science. A Turing machine performs operations on a tape—a string of symbols—of unlimited size. It contains instructions both for changing the symbols and for changing the symbol upon which it is operating. A simple Turing machine might have only the instruction "transform symbol to 1, then move right." This machine would output nothing but a string of 1's. This simple Turing machine is deterministic, but it is also possible to construct nondeterministic Turing machines that can perform several different operations given the same input.

These abstract machines can serve many purposes. They can be fun theoretical 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.

Ad

You might also Like

Recommended

Discuss this Article

Post your comments

Post Anonymously

Login

username
password
forgot password?

Register

username
password
confirm
email