| |||

## HOME## Theory of X-Machines- History of X-Machine Theory
- Physical Description
- When is a function X-computable?
- Monoids and X-machines
## Reference## MOTIVE |
## Physical Analogy of X-MachinesIn physical terms, an X-machine is simply a device or system for constructing, destroying or manipulating entities of type X. So, for example, a word processor is anelectronic-document-machine, and a calculator is a number-machine. While manipulating their
various objects, physical X-machines typically move between various states or modes of operation, and every
time the machine moves from one state to another it carries out some operation on the object. We can model
this situation very easily by drawing a collection of dots, one for each system state, and linking two states
with an arrow whenever it's possible for the X-machine to move from the first state to the second one. We
complete the model by identifying the activity carried out by the machine when it changes state in this way,
and labelling the arrow accordingly. Technically speaking, we also need to identify valid start and
stop states; these correspond to the way a machine typically starts up in a well-defined state every
time we turn it on, and ends up in another well-defined state whenever it completes the processing of an
object (or possibly back in the original state). The valid paths through the machine are the paths,
that start at a designated start state, traverse zero or more consecutive arrows, and end at a designated
stop state, and clearly, each such path corresponds to a meaningful and complete
set of operations on objects manipulated by the physical machine. The processing carried out on objects
during traversal of a valid path constitutes its associated path computation, and the machine is
deemed capabale of "computing" anything that can be achieved by executing one or other of its various
path computations.
A collection of nodes which are joined in this way by labelled arrows is generally called a
For our purposes, we need to assume that the physical attributes that identify objects as being of type X can
be modelled mathematically, and that every activity carried out by an X-machine can be modelled as a relation
on (the mathematical representation of) X. In this situation, where the labels of a finite state machine are
interpreted as relations on a set X, and traversing first one arrow and then another represents the application
of consecutive functions and relations, we call the model a (theoretical) |