Consider a cellular automaton in one dimension, having m letters as the states of the constituent finite state automata, called cells. It is shown that, once the number of neighbors connected to each cell is fixed, there exist periodic sequences in m letters such that the cellular automaton is not capable of transforming them in one step into periodic sequences in $(m - 1)$ letters, preserving at the same time their primitive periods, regardless of the choices of transformation functions. Our proof is by the construction of sequences which prevent any given cellular automaton from performing the task.

The late John von Neumann took an interest in a mechanical modeling of self-reproducing phenomena of living things, which are far more complex and purposeful than a mere regeneration of a facsimile of the structures found, for example, in the growth of a crystal in a solution of the constituent substance. After some initial work with some kinematic models of such phenomena, he found a two-dimensional array of identical finite-state machines to be a convenient medium in which to study self- reproducing phenomena represented as the successive state distributions of finite state machines[1].

A mathematical framework is defined in which many questions concerning uniform arrays of finite-state machines can be formulated and studied. An outline is then presented that informally describes some research areas that have been under investigation. Some of the results uncovered to date are described and many open problems are stated.

Three notions are introduced: 1) a class of logic nets with ``disjunctively linear structure,'' 2) ``disjunctively linear behavior'' or logic nets, and 3) ``position diagrams'' to represent logic nets. Through the study of their properties, it is shown that there is a close relationship between disjunctively linear structures and the behavior of logic nets. It is then shown that the state diagrams of Moore and Mealy and the regular expression of Kleene can be considered as particular manifestations of the notion of disjunctive linearity. By means of the notion of disjunctive linearity, a unified treatment is given to state diagrams by Mealy and the logic nets constructed by Copi, Elgot, and Wright from regular expressions. Finally, a discussion is given to the normal form and the position diagram providing a technique for describing disjunctively linear logic nets. Some problems, such as the practical application of disjunctively linear logic nets for hazard-free operation and the minimization of regular expressions through the use of position diagrams, are suggested.

As an attempt to investigate a general theory of real-time computability in digital computers, a subclass of Turing machines is formally introduced together with some classes of functions that are computable by them in real time. Then the existence is established of a class of recursive functions that are not computable in real time by use of a class of machines, no matter how general we make the machines subject to a given constraint.

Algorithms are presented for 1) converting a state graph describing the behavior of an automaton to a regular expression describing the behavior of the same automaton (section 2), and 2) for converting a regular expression into a state graph (sections 3 and 4). These algorithms are justified by theorems, and examples are given. The first section contains a brief introduction to state graphs and the regular-expression language.