On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
- 1 July 1969
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 16 (3) , 407-422
- https://doi.org/10.1145/321526.321530
Abstract
It is suggested that there are innite computable sets of natural numbers with the property that no innite subset can be computed more simply or more quickly than the whole set. Attempts to establish this without restricting in any way the computer involved in the calculations are notKeywords
This publication has 9 references indexed in Scilit:
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1969
- On the size of machinesInformation and Control, 1967
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- Machine dependence of degrees of difficultyProceedings of the American Mathematical Society, 1965
- Degrees of Unsolvability. (AM-55)Published by Walter de Gruyter GmbH ,1964
- A formal theory of inductive inference. Part IInformation and Control, 1964
- Retraceable SetsCanadian Journal of Mathematics, 1958