Gregory J. Chaitin
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.
- 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
Index Terms
- On the Length of Programs for Computing Finite Binary Sequences
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