Moore machine: Facts, Discussion Forum, and Encyclopedia Article

All Topics

Moore machine

	Email		Print
	Bookmark		Link

	Moore machine
	Home Discussion
	Topics Moore machine Topic Home In the theory of computationTheory of computation The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solv... , a Moore machine is a finite state automaton where the outputs are determined by the current stateState (computer science) Summary In information processing, a state is the complete set of properties transmitted by an object to an observer via one or more... alone (and do not depend directly on the input). The state diagramState diagram State diagrams are used to graphically represent finite state machines.... for a Moore machine will include an output signal for each state. Compare with a Mealy machineMealy machine In the theory of computation, a Mealy machine is a type of transducer, a finite state machine that generates an output for e... , which maps transitions in the machine to outputs. The name Moore machine comes from that of its promoter, Edward F. MooreEdward F. Moore Edward F. Moore was a professor of mathematics and computer sciences at the University of Wisconsin-Madison from 1966 until ... , a state-machine pioneer who wrote "Gedanken-experiments on Sequential Machines". Most digital electronic systems are designed as clocked sequential systemClocked sequential system In digital electronics, a clocked sequential system is a system whose output depends only on the current state, whose state change... s. Clocked sequential systems are a restricted form of Moore machine where the state changes only when the global clock signal changes. Typically the current state is stored in flip-flopsFlip-flop (electronics) In electronics and digital circuits, the flip-flop or bistable multivibrator is a pulsed digital circuit capable of se... , and a global clock signal is connected to the "clock" input of the flip-flops. Clocked sequential systems are one way to solve metastabilityMetastability in electronics Metastability in electronics is the ability of a non-equilibrium electronic state to persist for a long period of time. ... problems. A typical electronic Moore machine includes a combinatorial logic chain to decode the current state into the outputs (lambda). The instant the current state changes, those changes ripple through that chain, and almost instantaneously the outputs change (or don't change). There are design techniques to ensure that no glitchGlitch A glitch is a short-lived fault in a system.... es occur on the outputs during that brief period while those changes are rippling through the chain, but most systems are designed so that glitches during that brief transition time are ignored or are irrelevant. The outputs then stay the same indefinitely, until the Moore machine changes state again. Formal definition A Moore machine can be defined as a 6-tuple ( S, S₀, S, ?, T, G ) consisting of the following: a finite set of states ( S ) a start state (also called initial state) S₀ which is an element of (S) a finite set called the input alphabet ( S ) a finite set called the output alphabet ( ? ) a transition functionFunction (mathematics) In mathematics, a function relates each of its inputs to exactly one output.... (T : S × S ? S) mapping a state and the input alphabet to the next state an output function (G : S ? ?) mapping each state to the output alphabet The number of states in a Moore machine will be greater than or equal to the number of states in the corresponding Mealy machine. The number of states in a Mealy machine will be less than or equal to the number of states in the corresponding Moore machine. Gedanken-experiments (Gedanke = thought) In Moore's paper "Gedanken-experiments on Sequential Machines" [1], the (n;m;p) automata (or machines) S are defined as having n states, m input symbols and p output symbols. Nine theorems are proved about the structure of S, and experiments with S. Later, S machines became known as Moore machines. At the end of the paper, in Section Further problems, the following task is stated: Another directly following problem is the improvement of the bounds given at the theorems 8 and 9. Moore's Theorem 8 is formulated as: Given an arbitrary (n;m;p) machine S, such that every two of its states are distinguishable from one another, then there exists an experiment of length ' which determines the state of S at the end of the experiment. In 1957 A.A. Karatsuba proved the following two theorems, which completely solved Moore's problem on the improvement of the bounds of the experiment length of his Theorem 8. Theorem A. If S is an (n;m;p) machine, such that every two of its states are distinguishable from one another, then there exists a branched experiment of length at most ' through which one may determine the state of S at the end of the experiment. Theorem B. There exists an (n;m;p) machine, every two states of which are distinguishable from one another, such that the length of the shortest experiments establishing the state of the machine at the end of the experiment is equal to . Theorems A and B were used for the basis of the course work of a student of the fourth year, A.A. Karatsuba, "On a problem from the automata theory" which was distinguished by testimonial reference at the competition of student works of the faculty of mechanics and mathematics of Moscow Lomonosow State University in 1958. The paper by A.A. Karatsuba was given to the journal Uspekhi Mat. Nauk on 17 December 1958 and was published there in June 1960 . Until the present day (2007), Karatsuba's result on the length of experiments is the only exact nonlinear result, both in automata theory, and in similar problems of computational complexity theory. See also Synchronous circuitSynchronous circuit A synchronous circuit is a digital circuit in which the parts are synchronized by a clock signal.... Mealy machineMealy machine In the theory of computation, a Mealy machine is a type of transducer, a finite state machine that generates an output for e...