On the Length of Programs for Computing Finite Binary Sequences

On the Length of Programs for Computing Finite Binary Sequences

| GREGORY J. CHAITIN
The paper by Gregory J. Chaitin explores the use of Turing machines for calculating finite binary sequences from the perspectives of information theory and recursive function theory. The author examines the number of instructions in programs and introduces a modified form of Turing machine. The paper also discusses the impact of the number of symbols a Turing machine can write on its tape on the length of the required program. In Part 1, Chaitin defines an $N$-state $M$-tape-symbol Turing machine and shows that the length of the shortest program for calculating a given finite binary sequence is asymptotically proportional to $NM \log_2 N$. He also proves that at least $1/M$ of the bits in a program are redundant. In Part 2, a major alteration is made to the logical design of the Turing machine, introducing a fixed upper bound on the length of transfers between program parts. This leads to a discussion on the "local" and "global" behavior of the length of programs for calculating binary sequences. In Part 3, Chaitin defines a random or patternless binary sequence and proposes a definition based on the length of programs required to compute them. The paper concludes with an application of these concepts to the problem of defining a patternless sequence.The paper by Gregory J. Chaitin explores the use of Turing machines for calculating finite binary sequences from the perspectives of information theory and recursive function theory. The author examines the number of instructions in programs and introduces a modified form of Turing machine. The paper also discusses the impact of the number of symbols a Turing machine can write on its tape on the length of the required program. In Part 1, Chaitin defines an $N$-state $M$-tape-symbol Turing machine and shows that the length of the shortest program for calculating a given finite binary sequence is asymptotically proportional to $NM \log_2 N$. He also proves that at least $1/M$ of the bits in a program are redundant. In Part 2, a major alteration is made to the logical design of the Turing machine, introducing a fixed upper bound on the length of transfers between program parts. This leads to a discussion on the "local" and "global" behavior of the length of programs for calculating binary sequences. In Part 3, Chaitin defines a random or patternless binary sequence and proposes a definition based on the length of programs required to compute them. The paper concludes with an application of these concepts to the problem of defining a patternless sequence.
Reach us at info@study.space
[slides] On the Length of Programs for Computing Finite Binary Sequences | StudySpace