Total complexity and the inference of best programs.
Abstract/Contents
- Abstract
- Axioms for a total complexity measure for abstract programs are presented. Essentially, they require that total complexity be an unbounded increasing function of the Blum time and size measures. Algorithms for finding the best program on a finite domain are presented, and their limiting behaviour for infinite domains described. For total complexity, there are important senses in which a machine $underline{can}$ find the best program for a large class of functions.
Description
| Type of resource | text |
|---|---|
| Form | technical reports |
| Extent | 1 text file |
| Place | Stanford (Calif.) |
| Date created | April 1, 1972 |
| Language | English |
| Digital origin | reformatted digital |
Creators/Contributors
| Author | Feldman, Jerome A. |
|---|
Subjects
| Subject | Stanford University. Computer Science Department |
|---|---|
| Subject | Computer science |
| Genre | Technical reports |
Bibliographic information
| Finding Aid | |
|---|---|
| Technical Report # | CS-TR-1972-253 |
| Location | https://purl.stanford.edu/bf090tb3193 |
| Location | 3840/2 |
| Repository | Stanford University. Libraries. Department of Special Collections and University Archives |
Access conditions
- Use and reproduction
- The materials are open for research use and may be used freely for non-commercial purposes with an attribution. For commercial permission requests, please contact the Stanford University Archives (universityarchives@stanford.edu).
Collection
Stanford Artificial Intelligence Laboratory records, 1963-2009
View other items in this collection in SearchWorksStanford University, Department of Computer Science, Technical Reports
View other items in this collection in SearchWorksAlso listed in
Loading usage metrics...