article

Free access

On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers

Author:

Gregory J. ChaitinAuthors Info & Claims

Journal of the ACM (JACM), Volume 16, Issue 3

Pages 407 - 422

https://doi.org/10.1145/321526.321530

Published: 01 July 1969 Publication History

PDF eReader

References

[1]

HARDY, G. H., AND WRIGHT, E.M. An Introduction to the Theory of Numbers. Clarendon Press, Oxford, 1962.

Google Scholar

[2]

DANTZIG, T. Number, the Language of Science. Macmillan, New York, 1954.

Google Scholar

[3]

DAvis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.

Google Scholar

[4]

GELFOND, A. O., AND LINmK, Yu. V. Elementary Methods in Analytic Number Theory. Rand McNally, Chicago, 1965.

Google Scholar

[5]

BLUM, M. Measures on the computation speed of partial recursive functions. Quart. Prog. Rep. 72, Res. Lab. Electronics, MIT, Cambridge, Mass., Jan. 1964, pp. 237-253.

Google Scholar

[6]

ARBIB, M. A. Speed-up theorems and incompleteness theorems. In Automata Theory, E. R. Cainiello (Ed.), Academic Press, New York, 1966, pp. 6-24.

Google Scholar

[7]

FRAENKEL, A. A. Abstract Set Theory. North-Holland, Amsterdam, The Netherlands, 1961.

Google Scholar

[8]

BOREL, R. Lemons sur la Th.orie des Fonctions. Gauthier-Villars, Paris, 1914.

Google Scholar

[9]

HARDY, G. H. Orders of Infinity. Cambridge Math. Tracts, No. 12, U. of Cambridge, Cambridge, Eng., 1924.

Google Scholar

[10]

Dekker, J. C. E., AND MYIILL, J. Retraceable sets. Canadian J. Math. 10 (1958), 357-373.

Google Scholar

[11]

SOLOMONOFF, R.J. A formal theory of inductive inference, Pt. I. Inform. Contr. 7 (1964), 1-22.

Google Scholar

[12]

KOLMOGOROV, A.N. Three approaches to the definition of the concept "amount of information." Problemy Peredachi Informatsii I (1965), 3-11. (Russian)

Google Scholar

[13]

CHAITIN, G.J. On the length of programs for computing finite binary sequences: statistical considerations. J. ACM 16, 1 (Jam 1969), 145-159.

Crossref

Google Scholar

[14]

ARBIR, M. A., AND BLUM, M. Machine dependence of degrees of difficulty. Proc. Amer. Math. Soc. 16 (1965), 442-447.

Google Scholar

[15]

BIRKHOFF, G. Lattice Theory. Amer. Math. Soc. Colloq. Publ. Vol. 25, Amer. Math. Soc., Providence, R. I., 1967.

Google Scholar

[16]

CHAITIN, G.J. On the length of programs for computing ill, ire binary sequences. J. ACM 18, 4 (Oct. 1966), 547-569.

Crossref

Google Scholar

[17]

SACKS, G. E. Degrees of Unsolvability. No. 55, Annals of Math. Studies, Princeton U. Press, Princeton, N. J., 1963.

Google Scholar

[18]

HARTMANIS, J., AND STEARNS, R.E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285-306.

Google Scholar

[19]

BLUM, M. A machine-independent theory of the complexity of recursive functions. J. ACM 14, 2 (Apr. 1967), 322-336.

Crossref

Google Scholar

[20]

CHAITIN, G.J. A lattice of computer speeds. Abstract 67T-397, Notices Amer. Math. Soc. 14 (1967), 538.

Google Scholar

[21]

MOSTOWSKI, A. ber gewisse universelle Relationen. Ann. Soc. Polon. Math. 17 (1938), 117-118.

Google Scholar

[22]

BLUM, M. Oil the size of machines. Inform. Contr. 11 (1967), 257-265.

Google Scholar

[23]

CHAITIN, G.J. On the difficulty of computations. Panamerican Symp. of Appl. Math., Buenos Aires, Argentina, Aug. 10, 1968. (to be published)

Google Scholar

Cited By

View all

Luo LStylios G(2024)Algorithmic Information Theory for the Precise Engineering of Flexible Material MechanicsMachine Learning and Knowledge Extraction10.3390/make60100126:1(215-232)Online publication date: 22-Jan-2024
https://doi.org/10.3390/make6010012
Mayer CLancet DMarkovitch O(2024)The GARD Prebiotic Reproduction Model Described in Order and ComplexityLife10.3390/life1403028814:3(288)Online publication date: 21-Feb-2024
https://doi.org/10.3390/life14030288
Mao XKotov N(2024)Complexity, disorder, and functionality of nanoscale materialsMRS Bulletin10.1557/s43577-024-00698-649:4(352-364)Online publication date: 12-Apr-2024
https://doi.org/10.1557/s43577-024-00698-6
Show More Cited By

Index Terms

On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Numerical analysis
      1. Number-theoretic computations

Recommendations

Monoidal intervals of clones on infinite sets

Let X be an infinite set of cardinality @k. We show that if L is an algebraic and dually algebraic distributive lattice with at most 2^@k completely join irreducibles, then there exists a monoidal interval in the clone lattice on X which is isomorphic ...
Axiomatizing rational power series over natural numbers

Iteration semi-rings are Conway semi-rings satisfying Conway's group identities. We show that the semi-rings N^r^a^t<<@S^*>> of rational power series with coefficients in the semi-ring N of natural numbers are the free partial iteration semi-rings. ...
Some mathematical structures of generalized rough sets in infinite universes of discourse
Transactions on rough sets XIII

This paper presents a general framework for the study of mathematical structure of rough sets in infinite universes of discourse. Lower and upper approximations of a crisp set with respect to an infinite approximation space are first defined. Properties ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 16, Issue 3

July 1969

168 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321526

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1969

Published in JACM Volume 16, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
648
Total Downloads

Downloads (Last 12 months)95
Downloads (Last 6 weeks)15

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Luo LStylios G(2024)Algorithmic Information Theory for the Precise Engineering of Flexible Material MechanicsMachine Learning and Knowledge Extraction10.3390/make60100126:1(215-232)Online publication date: 22-Jan-2024
https://doi.org/10.3390/make6010012
Mayer CLancet DMarkovitch O(2024)The GARD Prebiotic Reproduction Model Described in Order and ComplexityLife10.3390/life1403028814:3(288)Online publication date: 21-Feb-2024
https://doi.org/10.3390/life14030288
Mao XKotov N(2024)Complexity, disorder, and functionality of nanoscale materialsMRS Bulletin10.1557/s43577-024-00698-649:4(352-364)Online publication date: 12-Apr-2024
https://doi.org/10.1557/s43577-024-00698-6
Hromkovič J(2024)Kolmogorov complexity and nondeterminism versus determinism for polynomial time computationsTheoretical Computer Science10.1016/j.tcs.2024.1147471013(114747)Online publication date: Oct-2024
https://doi.org/10.1016/j.tcs.2024.114747
Stanisz TDrożdż SKwapień J(2024)Complex systems approach to natural languagePhysics Reports10.1016/j.physrep.2023.12.0021053(1-84)Online publication date: Feb-2024
https://doi.org/10.1016/j.physrep.2023.12.002
Costa DRocha EFerreira N(2024)Estimating data complexity and drift through a multiscale generalized impurity approachJournal of Computational Mathematics and Data Science10.1016/j.jcmds.2024.10009812(100098)Online publication date: Sep-2024
https://doi.org/10.1016/j.jcmds.2024.100098
Ji RYan MZhao MGeng Y(2024)Construction of pan-cancer regulatory networks based on causal inferenceBioSystems10.1016/j.biosystems.2024.105279243(105279)Online publication date: Sep-2024
https://doi.org/10.1016/j.biosystems.2024.105279
Brandt N(2024)Lower Bounds for Levin–Kolmogorov ComplexityTheory of Cryptography10.1007/978-3-031-78011-0_7(191-221)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-78011-0_7
Ehresmann ABéjean MVanbremeersch J(2023)A Mathematical Framework for Enriching Human–Machine InteractionsMachine Learning and Knowledge Extraction10.3390/make50200345:2(597-610)Online publication date: 6-Jun-2023
https://doi.org/10.3390/make5020034
Mayer C(2023)Order and Complexity in the RNA WorldLife10.3390/life1303060313:3(603)Online publication date: 21-Feb-2023
https://doi.org/10.3390/life13030603
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Monoidal intervals of clones on infinite sets

Axiomatizing rational power series over natural numbers

Some mathematical structures of generalized rough sets in infinite universes of discourse

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations