1969/07/01 by Gregory J. Chaitin · 5 citations
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #semigroups and automata theory #Benford’s Law and Fraud Detection
paper · pdf · doi:10.1145/321526.321530
openalex publication_date 1969/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/05
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.