On the Length of Programs for Computing Finite Binary Sequences

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.
• 2: ---. A mathematical theory of communication. Bell Syst. Tech. J. 27 (1948), 379-423.
• 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-
• 4: DAVIS, M. Comutability and Unsolvaility McGraw-Hilt, New York, 1958.
• 5: NOV MIUSES, R Probability, Statistics and Tmzth. MacMillan, New York, 19219.
• 6: WALD, A. Die Widempmmhsfreiheit des Koltektivbeg:riffes der Wahrscheialichkeitsrech mmg. Ergcbnisse eines mathe:matischen Kolloquiums 8 (1937), 38-72.
• 7: CHURCH A. Or the concep of a random sequence. Bull, Amer. Math. Soc. 6 (1940), 130- I35.
• 8: POPERR, K.R. The Logic 4 Scientfic Discovery. O. of Toronto Press, Toronto:, 1959.
• 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.
• 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.
• 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.")

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

General Terms:
Design, Measurement, Performance, Theory, Verification