The X-machine (XM) is a theoretical model of computation introduced by Samuel Eilenberg in 1974. The X in "X-machine" represents the fundamental 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 (computing a set of changes to the data type X), and traversing a path in the machine corresponds to applying all the associated relations, one after the other.
Original theory Eilenberg's original X-machine was a completely general theoretical model of computation (subsuming the Turing machine, for example), which admitted deterministic, non-deterministic and non-terminating computations. His seminal work published many variants of the basic X-machine model, each of which generalized the finite-state machine in a slightly different way. In the most general model, 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 (partial) relations φ: X → X. An X-machine is a finite-state machine whose arrows are labelled by relations in Φ. In any given state, one or more transitions may be enabled if the domain of the associated relation φi accepts (a subset of) the current values stored in X. In each cycle, all enabled transitions are assumed to be taken. 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 the behaviours computed by its path relations. In general, this is non-deterministic, since applying any relation computes a set of outcomes on X. In the formal model, all possible outcomes are considered together, in parallel. For practical purposes, an X-machine should describe some finite computation. An encoding function α: Y → X converts from some input data type Y into the initial state of X, and a decoding function β: X → Z, converts back from the final state(s) of X into some output data type Z. Once the initial state of X is populated, the X-machine runs to completion, and the outputs are then observed. In general, a machine may deadlock (be blocked), or livelock (never halt), or perform one or more complete computations. For this reason, more recent research has focused on deterministic X-machines, whose behaviour can be controlled and observed more precisely.
Example A compiler with a peep-hole optimizer can be thought of as a machine for optimizing program structure. In this Optimizer-machine, the encoding function α takes source code from the input-type Y (the program source) and loads it into the memory-type X (a parse tree). Suppose that the machine has several states, called FindIncrements, FindSubExprs and Completed. The machine starts in the initial state FindIncrements, which is linked to other states via the transitions:
FindIncrements →DoIncrement FindIncrements FindIncrements →SkipIncrement FindSubExprs FindSubExprs →DoSubExpr FindSubExprs FindSubExprs →SkipSubExpr Completed
The relation DoIncrement maps a parsed subtree corresponding to "x := x + 1" into the optimized subtree "++x". The relation DoSubExpr maps a parse tree containing multiple occurrences of the same expression "x + y ... x + y" into an optimized version with a local variable to store the repeated computation "z := x + y; ... z ... z". These relations are only enabled if X contains the domain values (subtrees) on which they operate. The remaining relations SkipIncrement and SkipSubExpr are nullops (identity relations) enabled in the complementary cases. So, the Optimizer-machine will run to completion, first converting trivial additions into in-place increments (while in the FindIncrements state), then it will move on to the FindSubExprs state and perform a series of common sub-expression removals, after which it will move to the final state Completed. The decoding function β will then map from the memory-type X (the optimized parse-tree) into the output-type Z (optimized machine code).
Convention When referring to Eilenberg's original model, "X-machine" is typically written with a lower-case "m", because the sense is "any machine for processing X". When referring to later specific models, the convention is to use a capital "M" as part of the proper name of that variant.
1980s Interest in the X-machine was revived in the late 1980s by Mike Holcombe, who noticed that the model was ideal for software formal 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. The structural simplicity of the model makes it extremely flexible; other early illustrations of the idea included Holcombe's specification of human-computer interfaces, his modelling of processes in cell biochemistry, and Stannett's modelling of decision-making in military command systems.
1990s X-machines have received renewed attention since the mid-1990s, when Gilbert Laycock's deterministic Stream X-Machine was found to serve as the basis for specifying large software systems that are completely testable. Another variant, the Communicating Stream X-Machine offers a useful testable model for biological processes and future swarm-based satellite systems.
2000s X-machines have been applied to lexical semantics by András Kornai, who models word meaning by `pointed' machines that have one member of the base set X distinguished. Application to other branches of linguistics, in particular to a contemporary reformulation of Pāṇini were pioneered by Gerard Huet and his co-workers
… excerpt ends here. Continue reading the full article.
