# Accession Number:

## AD0712843

# Title:

## BASIC THEORIES OF AUTOMATIC COMPUTATION.

# Descriptive Note:

## Final rept.,

# Corporate Author:

## STANFORD RESEARCH INST MENLO PARK CALIF

# Personal Author(s):

# Report Date:

## 1970-08-01

# Pagination or Media Count:

## 60.0

# Abstract:

The research effort under this contract concentrated on obtaining an insight into basic problems defining computation measure. A set of four papers represent the direct outcome of this effort. The first paper entitled On the Complexity of Programs relates succinctly the main conclusion of the investigation. It, in essence, implies that a generalized measure of complexity will not be found using the notion of complexity of programs. Arguments are given why fruitful strategy for future research will be to consider well-defined and relevant subclasses of computation and computation forms for which a natural measure might exist. The second paper is written in the above spirit. It is entitled A Complexity Measure for Finite Automata, and it describes a method for the establishment of a complexity measure for the simplest class of computational devices, namely finite automate. This measure is particularly appealing because it implies a reduction to physically realizable canonical form with a natural separation between memory devices and memory-less logic. The third paper entitled On Winograds Algorithm for Inner Products, relates an important result in the quest for better procedures for operating on matrices. This result only adds a little to an area where much more knowledge is needed for efficient computation. Author

# Descriptors:

# Subject Categories:

- Statistics and Probability
- Computer Programming and Software