Computational complexity of recursive sequnces
- 1 November 1964
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper we investigate how numbers, functions, and sequences can be classified according to their computational complexity. The computational complexity is measured by how fast the number or function can be computed by a multitape computer (Turing machine). It is shown that by means of this measure the computational complexity of numbers and functions can be submitted to rigorous mathematical study and a number of results are obtained.Keywords
This publication has 6 references indexed in Scilit:
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Real time computationIsrael Journal of Mathematics, 1963
- Classes of Predictably Computable FunctionsTransactions of the American Mathematical Society, 1963
- Real-Time Computation and Recursive Functions Not Real-Time ComputableIEEE Transactions on Electronic Computers, 1962
- On certain formal properties of grammarsInformation and Control, 1959
- On Computable Numbers, with an Application to the EntscheidungsproblemProceedings of the London Mathematical Society, 1937