Kolmogorov-Complexity Based on Infinite Computations

We base the theory of Kolmogorov complexity on programs running on a special universal machine M, which computes infinite binary sequences x ? {0,1} ? . The programs are infinite sequences p ? {0,1}*·1·0 ? . As length |p| we define the length of the longest prefix of p ending with 1. We measure the distance d(x,y) = 2? n of x,y ? {0,1} ? by the length n of the longest common prefix of x and y. $\Delta_M(x,2^{-n})$ is the length of a minimal program p computing a sequence y with d(x,y) ≤ 2? n . It holds $\Delta_M(x,2^{-n})\leq\Delta_M(x,2^{-(n+1)})\leq n+2$ for all n. We prove that the sets of sequences $$ K_{\Delta_M} := \bigcup\limits_{c\in\mathcal{N}}\{x\in X^{\infty}:\Delta_M(x,2^{-n})>n-c\quad\textrm{for all n}\} $$ $$ K_{\Delta_M}^{o(n)} := \{x\in X^{\infty}:n+1-\Delta_M(x,2^{-n})=o(n)\} $$ have the measure 1 for memoryless sources with equal probabilities for 0 and 1. The sequences in $K_{\Delta_M}^{o(n)}$ are Bernoulli sequences. The sequences in $K_{\Delta_M}$ define collectives in the sense of von Mises up to a set of measure 0 and the sequences in $K_{\Delta_M}^{o(n)}$ have this property in a certain resricted fom.