The design and development of a universal computer in a four-state, five-neighbor cellular model is presented. The underlying structure of the model is an infinite two-dimensional space divided into unit cells each of which can be in one of four states 0, 1, 2, and x. State 0 is the quiescent state, states 1 and 2 are mainly used for signaling, while state x is used for structure purposes. Cells change states at discrete times according to a transition rule which determines the next state of a cell as a function of the present state of the cell itself and its four nondiagonal adjacent neighbors. A configuration is defined to be an assignment of states to all cells in the space such that only a finite number of cells are in the nonquiescent states. A set of configurations, called primitive elements, consisting of the wire, the junction, the corner, the delay, the extendible wire, and the crossover are introduced. Using these elements, a functionally complete set of configurations, called basic organs, comprised of the diode, the OR, the EXCLUSIVE-OR, the clock, and the NOT are developed. The primitive elements and the basic organs are utilized to design four general-purpose components—the encoder, the decoder, the recognizer, and the pulser. These components are used primarily for the detection and the generation of command instructions to and from the universal computer.

Critical races can be avoided in the binary encoding of asynchronous sequential machines by making use of general codes employing-multistep changes in secondary variables to accomplish transitions between states. The shortest length code of this type presently available is Huffman's internmeshed row set code, which encodes race-free any 2SO-row flow table with 2So-1 bits. In this paper, a new class of codes called augmented parity check codes (APC codes) is introduced and proposed for race-free encoding. Some of the properties of these codes suggest that minimum codes may require only on the order of So+ log2SObits.

This paper discusses some aspects of hazards in asynchronous sequential circuits. In particular, methods of hazard detection and correction are given for the analysis of circuits 1) designed by criteria other than hazard prevention, and/or 2) in which upper and lower bounds may be placed on delays. A natural ordering for sequential hazards is introduced as a basis for the procedures.