
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 welldefined 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 memoryless 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