Accession Number : AD0670544

Title :   ON COMPUTATIONAL SPEED-UP,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Meyer,Albert R. ; Fischer,Patrick C.

Report Date : MAY 1968

Pagination or Media Count : 24

Abstract : The 'operator speed up' in this paper establishes the existence of a computable function f such that for any program computing f(x) in a number of steps for all x, there is another program computing f(x) in a smaller number of steps. An example of speed up for Turing machines is considered.

Descriptors :   (*COMPUTER PROGRAMS, MATHEMATICAL ANALYSIS), (*FUNCTIONS(MATHEMATICS), MAPPING(TRANSFORMATIONS)), COMPUTATIONAL LINGUISTICS, RECURSIVE FUNCTIONS, OPERATORS(MATHEMATICS), ITERATIONS, THEOREMS, COMPUTER LOGIC

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE