Home | Physical Analogy of X-Machines X-Machines.Com


Theory of X-Machines



Physical Analogy of X-Machines

In 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 an electronic-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 labelled transition system (LTS), and if there are only finitely many nodes and arrows it's called a finite state machine (FSM). Nonetheless there is a key difference between finite state machines and the scenario described above, because the labels in an FSM are thought of as basic, passive, characters from some alphabet, whereas those we're using are the names of general-purpose activities.

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) X-machine. Formally speaking, each valid path corresponds to the relation on X obtained by composing the relations encountered as arrow-labels while traversing the path, and this composite relation is what we refered to above as the path computation. The relation computed by the machine is then the (set-theoretic) union of every possible path-computation.

Copyright © 2000-2013 Mike Stannett. All Rights Reserved.