On the efficiency of programs in subrecursive formalisms
- 1 October 1970
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We study the effect of program structure on computational efficiency in a class of abstract languages which model actual high-level numerical programming languages (like ALGOL). The results have bearing on programming technique (the use of go to statements), and they yield interesting facts about Blum's speed-up theorem for subrecursive computational complexity.Keywords
This publication has 12 references indexed in Scilit:
- On the size of programs in subrecursive formalismsPublished by Association for Computing Machinery (ACM) ,1970
- Classes of computable functions defined by bounds on computationPublished by Association for Computing Machinery (ACM) ,1969
- On effective procedures for speeding up algorithmsPublished by Association for Computing Machinery (ACM) ,1969
- On the size of machinesInformation and Control, 1967
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- The complexity of loop programsPublished by Association for Computing Machinery (ACM) ,1967
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Random-Access Stored-Program Machines, an Approach to Programming LanguagesJournal of the ACM, 1964
- A Hierarchy of Primitive Recursive FunctionsMathematical Logic Quarterly, 1963
- Primitive recursive functionsBulletin of the American Mathematical Society, 1947