Characterizations of the basic feasible functionals of finite type
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 154-159
- https://doi.org/10.1109/sfcs.1989.63471
Abstract
The authors define a simple typed while-programming language that generalizes the sort of simple language used in computability texts to define the familiar numerical computable functions and corresponds roughly to the mu -recursion of R.O. Gandy (1967). This language does not fully capture the notion of higher type computability. The authors define run times for their programs and prove that the feasible functionals of S. Cook and A. Urquhart (1988) are precisely those functionals computable by typed while-programs with run times feasibly length-bounded. The authors introduce the notion of a bounded typed loop program and prove that a finite type functional is feasible if it is computable by a bounded typed loop program.Keywords
This publication has 14 references indexed in Scilit:
- Polynomially graded logic I. A graded version of system TPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Pseudo-random generation from one-way functionsPublished by Association for Computing Machinery (ACM) ,1989
- The polynomial hierarchy and intuitionistic Bounded ArithmeticPublished by Springer Nature ,1986
- Computational complexity of real functionsTheoretical Computer Science, 1982
- Polynomial and abstract subrecursive classesJournal of Computer and System Sciences, 1976
- Type two computational complexityPublished by Association for Computing Machinery (ACM) ,1973
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Computable Functionals of Finite Type IPublished by Elsevier ,1967
- Turing-Machine Computable Functionals of Finite Types II†Proceedings of the London Mathematical Society, 1962
- Recursive Functionals and Quantifiers of Finite Types ITransactions of the American Mathematical Society, 1959