# 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

# Descriptors:

# Subject Categories:

- Theoretical Mathematics