Total Complexity and the Inference of Best Programs

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 can find the best program for a large class of functions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1972
Accession Number
AD0785171

Entities

People

  • J. A. Feldman
  • P. C. Shields

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Artificial Intelligence
  • Automata
  • Computations
  • Computer Science
  • Grammars
  • Humanities
  • Language
  • Literature
  • Machines
  • Mathematical Analysis
  • Natural Languages
  • Pattern Recognition
  • Recursive Functions
  • Schools
  • Sequences

Readers

  • Mathematical Modeling and Probability Theory.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms