On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
The work
| Authors | Gregory J. Chaitin |
|---|---|
| Editors | |
| Type | article |
| Year | 1969 |
| Citekey | chaitin1969simplicity |
Where it appeared
| Published in | Journal of the ACM |
|---|---|
| Publisher | Association for Computing Machinery |
| Volume | 16 |
| Issue | 3 |
| Pages | 407--422 |
Identifiers
| DOI | 10.1145/321526.321530 |
|---|---|
| OpenAlex | W1977165845 |
Access
| Landing page | https://doi.org/10.1145/321526.321530 |
|---|---|
| Free full text | https://dl.acm.org/doi/pdf/10.1145/321526.321530 |
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
Abstract
It is suggested that there are infinite computable sets of natural numbers with the property that no infinite 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 not entirely successful. A hypothesis concerning the computer makes it possible to exhibit sets without simpler subsets. A second and analogous hypothesis then makes it possible to prove that these sets are also without subsets which can be computed more rapidly than the whole set. It is then demonstrated that there are computers which satisfy both hypotheses. The general theory is momentarily set aside and a particular Turing machine is studied. Lastly, it is shown that the second hypothesis is more restrictive then requiring the computer to be capable of calculating all infinite computable sets of natural numbers.
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-10-23 11:20 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Filed under
Cite it as
@article{chaitin1969simplicity,
title = {On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers},
author = {Gregory J. Chaitin},
year = {1969},
journal = {Journal of the ACM},
publisher = {Association for Computing Machinery},
volume = {16},
number = {3},
pages = {407--422},
doi = {10.1145/321526.321530},
}
This record lives at https://refs.drheap.org/chaitin1969simplicity/ and will keep doing so.