Accession Number:

AD0649063

Title:

REALIZATION AND COMPLEXITY OF COMMUTATIVE EVENTS.

Descriptive Note:

Technical rept.,

Corporate Author:

MICHIGAN UNIV ANN ARBOR LOGIC OF COMPUTERS GROUP

Personal Author(s):

Report Date:

1967-03-01

Pagination or Media Count:

44.0

Abstract:

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE