Abstract :
In the search for understanding of the theoretical capabilities of computers and other decision-making logical machines, two abstract models have been found useful: finite-state machines and Turing machines. Roughly speaking, a finite-state machine emulates a collection of elemental bistable devices interconnected so that they exhibit a memory. A Turing machine consists of a finite-state circuit operating in conjunction with an infinite tape which it scans and upon which symbols are read, erased, and rewritten. Since the finite-state model is a component of even the Turing machine, a significant amount of effort has gone into the study of its organization, internal communication problems, and the complexity requisite to accomplishing various general transformations on the sequences of digits which constitute its input data. In the role of a sequence transducer between its input and output data streams the finite-state circuit (also called sequential circuit, or finite-state automaton, etc.) acts somewhat analogously to an electrical filter operating on voltage or current waveforms. That is the primary reason that the papers of this issue are found here rather than in, say, a mathematics journal. In this issue the paper by Seshu, Miller, and Metze investigates a matrix formulation of this statement and of some of its consequences. Unger examines in some detail the effects of stray delays in the elemental switching devices making up asynchronous sequential circuits. Simon shows some special properties of some sequential transducers which have simple forms of memory. In Cadden´s paper the question of equivalence of circuits whose data are presented in various forms, but which have the same ultimate design objective, is treated. A formal analysis of a quite general class of one-dimensional iterative circuits is set forth by Hennie. Since one subclass of these circuits is analogous to the conventional finite-state machine this paper may eventually lead to a better under- - standing both of finite-state circuits and also of uniform arrays of logical elements in more than one dimension. A comprehensive review of the present state of the art in linear sequential networks is the end-product of the paper by Elspas. The subject matter of the papers. by Friedland and Hartmanis is the extension of previous work on linear binary circuits to other number bases.
