REALIZATION AND COMPLEXITY OF COMMUTATIVE EVENTS.
MICHIGAN UNIV ANN ARBOR LOGIC OF COMPUTERS GROUP
Pagination or Media Count:
A measure of complexity is defined for a class of expressions denoting behaviors of commutative machines. For an expression of complexity m there is an m tape machine which realizes in real-time the event denoted. The machine realizations can be of many kinds the simplest realizations are those composed of finite counters of a single kind of input letter, combined with infinite state machines which check off numbers mod p of one kind of input letter against numbers mod r of a second kind of input letter. The state diagrams of the finite state machines are in the form of cycles possibly with linear lead-ins the state diagrams of the infinite state machines graphically are infinite cylinders possibly with two-dimensional lead in arrays. For any machine with m counter tapes as here defined, an m-complex expression can be obtained which denotes the event which is the behavior of the machine. Finally it is shown that for all m there are m-complex expressions which require m-counter tape machines for realizing in real-time the events denoted. Author
- Theoretical Mathematics