A proof concerning infinite nets of logic elements without feedback

Computers and other data processing equipments usually contain a basic pulse source (or clock) which keeps the various portions of the equipment in synchronization. When the size of the equipment increases significantly, however, or the clock frequency increases, the clock pulse can no longer be assumed to be at all portions of the hardware simultaneously and propagation delays for the clock pulse itself become important. An important problem is thus how to construct a logic net of nontrivial depth using real components (there are no zero delays and all delays can vary with time even if only slightly) into which a second (or-third, etc.), set of waveforms can be introduced before the first set of waveforms has propagated through to the end of the net. It has been shown by R. McNaughton that it is possible to construct such a net of unlimited depth without danger of one set of waveforms being destroyed by another set catching up with it, if the net contains signal feedback in which each logical element tells the preceding element or elements when it is ready to receive another waveform. The present paper proves that such a net cannot be achieved without such feedback. It is easy to show that the net of logic elements where each element merely delays the signal by a fixed amount (with some uncertainty in duration of the delay) can get into trouble, as one signal can catch up to another. However, if the element can contain memory elements (flipflops) to remember the relative timings of previous signals or if the element can buffer some number of successive input signals and be affected in its operation by their relative timing before passing on the first signal, or if the element can pass on control data to following (not preceding) elements, then the problem of showing a failure is more complicated. The present paper first defines rigorously the possible bounds on a physically-realizable element without feedback from following elements, and then shows that an arbitrarily, large chain. of such elements cannot be constructed to pass signals without a possible error.