Accession Number : AD0712843

Title :   BASIC THEORIES OF AUTOMATIC COMPUTATION.

Descriptive Note : Final rept.,

Corporate Author : STANFORD RESEARCH INST MENLO PARK CALIF

Personal Author(s) : Waksman,Abraham

Report Date : AUG 1970

Pagination or Media Count : 60

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)

Descriptors :   (*NUMERICAL ANALYSIS, COMPUTER PROGRAMMING), MATRICES(MATHEMATICS), INFORMATION THEORY, AUTOMATION, PROBABILITY, ALGORITHMS, THEOREMS

Subject Categories : Statistics and Probability
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE