BASIC THEORIES OF AUTOMATIC COMPUTATION.
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 Winograd's 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1970
- Accession Number
- AD0712843
Entities
People
- Abraham Waksman
Organizations
- SRI International