Jump to content

X-machine

Edit links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Mike.stannett (talk | contribs) at 22:20, 21 March 2008 (Added lots more information, including some history and details of other variants of the model. May need tidying.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The X-machine (XM) is a theoretical model of computation introduced by Samuel Eilenberg in 1974.[1] The X in "X-machine" represents the data type on which the machine operates; for example, a machine that operates on databases (objects of type database) would be a database-machine. The X-machine model is structurally the same as the finite state machine, except that the symbols used to label the machine's transitions denote relations of type X→X. Crossing a transition is equivalent to applying the relation that labels it, and traversing a path in the machine corresponds to applying the associated relations, one after the other.

While studying the model in the mid-to-late 1980s, Mike Holcombe noticed that the structure of the X-machine model makes it an ideal tool for specification purposes, because it cleanly separates control flow from processing. Provided one works at a sufficiently abstract level, the control flows in a computation can usually be represented as a finite state machine, so to complete the X-machine specification all that remains is to specify the processing associated with each of the machine's transitions.[2] The structural simplicity of the model makes it extremely flexible; other early illustrations of the idea included Holcombe's specification of human-computer interfaces,[3] and Stannett's modelling of decision-making in military command systems[4].

Formal definitions

An X-machine is essentially a "machine for manipulating objects of type X". Suppose that X is some datatype, called the fundamental datatype, and that Φ is a set of relations φ: X → X. An X-machine is a finite-state machine whose arrows are labelled by relations in Φ. Each recognised path through the machine generates a list φ1 ... φn of relations. We call the composition φ1 o ... o φn of these relations the path relation corresponding to that path. The behaviour of the X-machine is defined to be the union of all its path-behaviours. In other words, an X-machine can perform a manipulation just so long as one of its recognised paths can perform that computation.

Example

A word-processor can be thought of as a Document-machine, where Document is some data type representing documents. Typical processing relations might include A, a function that inserts the letter 'A' at the current cursor position.

Suppose the machine contains a state called Editing, representing the state in which editing of the document is allowed (as opposed to printing, saving, etc). For each of the letters A - Z, the machine will be equipped with an arrow from Editing to itself. That is, we'll have arrows 

 Editing   →A   Editing 
 Editing   →B   Editing 
 Editing   →C   Editing

and so on.

Suppose also that the keyboard has a special key marked Save, and that pressing Save takes the machine from the Editing state to the terminal state Saved. Hitting the Save button has no effect on the document itself - it simply changes machine state. We'd model it as the identity function (id) on documents. Likwise, we can imagine that the machine always starts up in edit-mode, so that Editing is the machine's initial state.

Now imagine that you're using the word processor to edit a document. One particular path from Editing to Saved would be

Editing →H Editing →E Editing →L Editing →L Editing →O Editing →id Saved

This path goes from the initial state Editing to the terminal state Saved, so it is recognised by the finite state machine, and contributes to the behaviour of the X-machine. The path relation computed by this path has the effect of inserting the word "HELLO" into the document.

Variants of the X-machine Model

The X-machine is rarely encountered in its original form, but underpins several subsequent models of computation. The earliest variant, the continuous-time Analog X-Machine (AXM), was introduced by Mike Stannett in 1990 as a potentially "super-Turing" model of computation;[5] it is consequently related to work in hypercomputation theory.[6] However, the most commonly encountered X-machine variant is Gilbert Laycock's 1993 Stream X-Machine (SXM) model,[7] which forms the basis for much work in the development of software that can be guaranteed to be testable.

Several X-machine variants have been proposed in the context of concurrent or parallel computing. NASA has recently discussed using a combination of X-machines and the process calculus WSCCS in the development of swarm satellite systems.[8] This model is expected to have features in common with the CCS-XM ("CCS-augmented X-machine") model developed by Simons and Stannett in 2002 to support complete behavioural testing of object-oriented systems,[9] but no definitive comparison of the two models has as yet been conducted. Another related approach (though again, no formal comparison has yet been undertaken) is embodied in Judith Barnard's 1996 Communicating X-machine (COMX or CXM) model,[10] in which machines are connected via named communication channels; this model exists in both discrete- and real-timed variants.[11] The CSXM (Communicating Stream X-Machine) model was first published in 1994, having been developed by Philip Bird as part of his PhD work, under the supervision of Tony Cowling. Cowling and his associates have continued to study the model, and have developed numerous applications. The CSXM model differs from Barnard's CXM in several ways; in particular, the machines communicate indirectly via a central nexus (essentially an array of pigeonholes) rather than directly via shared channels.[12][13]


References

  1. ^ S. Eilenberg (1974) Automata, Languages and Machines, Vol. A. Academic Press, London.
  2. ^ M. Holcombe (1988) 'X-machines as a basis for dynamic system specification', Software Engineering Journal 3(2), pp. 69-76.
  3. ^ M. Holcombe (1987) 'Formal methods in the specification of the human-machine interface', International J. Command and Control, Communications and Info. Systems. 1(2), pp. 24-34.
  4. ^ M. Stannett (1987) 'An organisational approach to decision-making in command systems.' International J. Command and Control, Communications and Info. Systems. 1(3), pp. 23-34.
  5. ^ M. Stannett (1990) 'X-machines and the Halting Problem: Building a super-Turing machine'. Formal Aspects of Computing 2, pp. 331-41.
  6. ^ B. J. Copeland (2002) 'Hypercomputation'. Minds and Machines 12, pp. 461-502.
  7. ^ Gilbert Laycock (1993) The Theory and Practice of Specification Based Software Testing. PhD Thesis, University of Sheffield. Abstract
  8. ^ M. G. Hinchey, C. A. Rouff, J. L. Rash and W. F. Truszkowski (2005) "Requirements of an Integrated Formal Method for Intelligent Swarms", in Proceedings of FMICS'05, September 5–6, 2005, Lisbon, Portugal. Association for Computing Machinery, pp. 125-133.
  9. ^ M. Stannett and A. J. H. Simons (2002) CCS-Augmented X-Machines. Technical Report CS-2002-04, Dept of Computer Science, Sheffield University, UK.
  10. ^ J. Barnard (1996) COMX: A methodology for the formal design of computer systems using Communicating X-machines. PhD Thesis, Staffordshire University.
  11. ^ A. Alderson and J. Barnard (1997) 'On Making a Crossing Safe'. Technical Report SOCTR/97/01, School of Computing, Staffordshire University. (Citeseer)
  12. ^ P. R. Bird and A. J. Cowling (1994) "Modelling Logic Programming Using a Network of Communicating Machines", in Proc. 2nd Euromicro Workshop on Parallel and Distributed Processing, Malaga, 26-28 January 1994, pages 156 - 161. Abstract
  13. ^ A. J. Cowling (2005) "A Formal Model for Test Frames", in P. McMinn (ed.), Proc. UK Software Testing Conference 2005, Sheffield, 5-6 September 2005, pp. 83-98. (Available online)
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=X-machine&oldid=199931553"