Coding and Computation
Łukasz Dębowski · 2020
This chapter commences with the basic ideas of coding and then proceeds towards the algorithmic information theory. It introduces Turing machines, a traditional mathematical model of a general purpose computer. The chapter defines the Kolmogorov complexity of an object as the length of the shortest binary program for a universal Turing machine that computes a binary representation of this object. It presents parallels between Kolmogorov complexity and Shannon entropy. The algorithmic information theory sheds some light onto the limits of mathematics. The chapter discusses the Chaitin incompleteness theorem, which complements the famous incompleteness theorem by Godel. An infinite sequence is called algorithmically random with respect to a probability measure on sequences when the Kolmogorov complexity of its prefixes is close to the probability of the respective cylinder sets. This property holds for almost all sequences, so there are really uncountably many different algorithmically random sequences.