|
The X-machine (''XM'') is a theoretical model of computation introduced by Samuel Eilenberg in 1974.〔 name="Eil74">S. Eilenberg (1974) ''Automata, Languages and Machines, Vol. A''. Academic Press, London.〕 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. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「X-machine」の詳細全文を読む スポンサード リンク
|