article

Free access

On the Length of Programs for Computing Finite Binary Sequences

Author:

Gregory J. ChaitinAuthors Info & Claims

Journal of the ACM (JACM), Volume 13, Issue 4

Pages 547 - 569

https://doi.org/10.1145/321356.321363

Published: 01 October 1966 Publication History

PDF eReader

Abstract

The use of Turing machines for calculating finite binary sequences is studied from the point of view of information theory and the theory of recursive functions. Various results are obtained concerning the number of instructions in programs. A modified form of Turing machine is studied from the same point of view. An application to the problem of defining a patternless sequence is proposed in terms of the concepts here developed.

References

[1]

SHANON, C. E. A universal Tvring machine with two internal states. In Automata Sludiea, Shagreen aNd McCarthy, Edm, Primeton U. Press, Princeton, N. J., 1956.

Google Scholar

[2]

---. A mathematical theory of communication. Bell Syst. Tech. J. 27 (1948), 379-423.

Google Scholar

[3]

TURNING, A. M. O computable mlmbers, with an application to the Entscheidungsproblare. Prec. London Math. See. {2}2 (19337), 230=265; Correction, ibid, 43 (1937), 544-

Google Scholar

[4]

DAVIS, M. Comutability and Unsolvaility McGraw-Hilt, New York, 1958.

Google Scholar

[5]

NOV MIUSES, R Probability, Statistics and Tmzth. MacMillan, New York, 19219.

Google Scholar

[6]

WALD, A. Die Widempmmhsfreiheit des Koltektivbeg:riffes der Wahrscheialichkeitsrech mmg. Ergcbnisse eines mathe:matischen Kolloquiums 8 (1937), 38-72.

Google Scholar

[7]

CHURCH A. Or the concep of a random sequence. Bull, Amer. Math. Soc. 6 (1940), 130- I35.

Google Scholar

[8]

POPERR, K.R. The Logic 4 Scientfic Discovery. O. of Toronto Press, Toronto:, 1959.

Google Scholar

[9]

VON NEUMANN, J. Various techniques used in connection with random digits. In John yon Neumann, Collected Works, Vol. V, A. H. Taub, Ed, MacMillan, New York, 1963.

Google Scholar

[10]

CHAITAN, G. J. On the length of programs for computing finite binary sequences by bounded-transfer Taring machines. Abstract 66T-26, Notic. Amer. Math. Soc. 13 (I966), 133.

Google Scholar

[11]

---. On the length of programs for eompating finite binary sequenees by bounded.trans_ far Turing machines II. Atmtract 631-6, Notic. Amer. Math. Soc. i8 (1966), 228-22(3. (Erratum, p. 229, line 5: replace "P" by "L.")

Google Scholar

Cited By

View all

Wheeler WVarón A(2025)Phylogenetic minimum description length: an optimality criterion based on algorithmic complexityCladistics10.1111/cla.12603Online publication date: 16-Feb-2025
https://doi.org/10.1111/cla.12603
Tlusty TLibchaber A(2025)Life sets off a cascade of machinesProceedings of the National Academy of Sciences10.1073/pnas.2418000122122:4Online publication date: 24-Jan-2025
https://doi.org/10.1073/pnas.2418000122
Melkikh A(2025)Progressive evolution of plants: a critical reviewBioSystems10.1016/j.biosystems.2025.105444(105444)Online publication date: Mar-2025
https://doi.org/10.1016/j.biosystems.2025.105444
Show More Cited By

Index Terms

On the Length of Programs for Computing Finite Binary Sequences
1. Mathematics of computing

Recommendations

On the Length of Programs for Computing Finite Binary Sequences: statistical considerations

An attempt is made to carry out a program (outlined in a previous paper) for defining the concept of a random or patternless, finite binary sequence, and for subsequently defining a random or patternless, infinite binary sequence to be a sequence whose ...
New optimal binary sequences with period 4p via interleaving Ding---Helleseth---Lam sequences

Binary sequences play important roles in radar, communication, and cryptography. Finding new binary sequences with optimal autocorrelation value/magnitude has been an interesting research topic in sequence design. Ding---Helleseth---Lam sequences are ...
Low autocorrelation binary sequences: Number theory-based analysis for minimum energy level, Barker codes

Low autocorrelation binary sequences (LABS) are very important for communication applications. And it is a notoriously difficult computational problem to find binary sequences with low aperiodic autocorrelations. The problem can also be stated in terms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 13, Issue 4

Oct. 1966

159 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321356

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1966

Published in JACM Volume 13, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

739
Total Citations
View Citations
1,666
Total Downloads

Downloads (Last 12 months)325
Downloads (Last 6 weeks)38

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wheeler WVarón A(2025)Phylogenetic minimum description length: an optimality criterion based on algorithmic complexityCladistics10.1111/cla.12603Online publication date: 16-Feb-2025
https://doi.org/10.1111/cla.12603
Tlusty TLibchaber A(2025)Life sets off a cascade of machinesProceedings of the National Academy of Sciences10.1073/pnas.2418000122122:4Online publication date: 24-Jan-2025
https://doi.org/10.1073/pnas.2418000122
Melkikh A(2025)Progressive evolution of plants: a critical reviewBioSystems10.1016/j.biosystems.2025.105444(105444)Online publication date: Mar-2025
https://doi.org/10.1016/j.biosystems.2025.105444
Folkman LPitt KStantic B(2025)A data-centric framework for combating domain shift in underwater object detection with image enhancementApplied Intelligence10.1007/s10489-024-06224-055:4Online publication date: 4-Jan-2025
https://dl.acm.org/doi/10.1007/s10489-024-06224-0
Tong Qixia 童Hu Yingying 胡He Deyong 何Han Zhengfu 韩(2024)自发辐射放大的量子随机数快速后处理方法Laser & Optoelectronics Progress10.3788/LOP23083961:5(0527001)Online publication date: 2024
https://doi.org/10.3788/LOP230839
Lemus MFaleiro RMateus PPaunković NSouto A(2024)Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machinesQuantum10.22331/q-2024-01-18-12308(1230)Online publication date: 18-Jan-2024
https://doi.org/10.22331/q-2024-01-18-1230
Soto EEmonet RSebban M(2024)Unsupervised Learning and Effective Complexity: Introducing JPG and Neural Sophistication2024 IEEE 36th International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI62512.2024.00040(221-225)Online publication date: 28-Oct-2024
https://doi.org/10.1109/ICTAI62512.2024.00040
Zhang ZLiu CZhu YPeng LQiu WTang QLiu HZhang KDi ZLiu Y(2024)Evolutionary tinkering enriches the hierarchical and nested structures in amino acid sequencesPhysical Review Research10.1103/PhysRevResearch.6.0232156:2Online publication date: 28-May-2024
https://doi.org/10.1103/PhysRevResearch.6.023215
Scharf CWitkowski O(2024)Rebuilding the Habitable Zone from the Bottom up with Computational ZonesAstrobiology10.1089/ast.2023.003524:6(613-627)Online publication date: 1-Jun-2024
https://doi.org/10.1089/ast.2023.0035
Łukaszyk S(2024)Life as the Explanation of the Measurement ProblemJournal of Physics: Conference Series10.1088/1742-6596/2701/1/0121242701:1(012124)Online publication date: 1-Feb-2024
https://doi.org/10.1088/1742-6596/2701/1/012124
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.

Abstract

References

Cited By

Index Terms

Recommendations