Algorithmic Chaos
CWI and Universiteit van Amsterdam
Many physical theories like chaos theory are fundamentally concerned with the conceptual tension between determinism and randomness. Kolmogorov complexity can express randomness in determinism and gives an approach to formulate chaotic behavior.
nlin0303016.tex
\documentstyle{article} % line 642
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9in}
\setlength{\footskip}{0.5in}
\setlength{\parskip}{2pt plus 2pt minus 2pt}


\title{Algorithmic Chaos}

\author{
Paul M.B. Vit\'{a}nyi\thanks{This paper is based
on a talk by the author at the University of Waterloo, Canada, in 1991.
Partially supported by EU through NeuroColt II Working Group 
and the QAIP Project.
Address: Centrum voor Wiskunde en Informatica,
Kruislaan 413, 1098 SJ Amsterdam, The Netherlands. Email: paulv@cwi.nl}\\
CWI and Universiteit van Amsterdam}

%\input{/usr/local/lib/tex/macros/psfig}

\newtheorem{theo}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newenvironment{comment}{\begin{small} \begin{quotation}}{\end{quotation} \end{small}}
\newenvironment{proof}{\par \sc Proof. \rm}{$\Box$ \vspace{1ex}}


\newcommand{\nat}{I\!\!N}
\newcommand{\ar}{\rightarrow}
\newcommand{\arp}{\Rightarrow}

\newcommand{\pcs}[1]{\mbox{process}(#1)}

\newcommand{\half}{\frac{1}{2}}
\newcommand{\free}{\bot}
\newcommand{\pos}{\mbox{pos}}
\newcommand{\heads}{\mbox{heads}}
\newcommand{\tails}{\mbox{tails}}

\newcommand{\s}[1]{s(#1)}
\newcommand{\f}[1]{f(#1)}
\newcommand{\sa}[2]{#1.#2}
\newcommand{\Hi}{H {\infty}}

\newcommand{\rst}{\mbox{\it rst\/}}
\newcommand{\me}{\mbox{\it me\/}}
\newcommand{\he}{\mbox{\it he\/}}
\newcommand{\chose}{\mbox{\it choose\/}}

\newcommand{\jump}{\hspace*{1em}}

\newcommand{\chooose}[2]{\left( \begin{array}{c} #1 \\ #2 \end{array} \right)}
\newcommand{\defic}{\delta}
\newcommand{\C}{C}
\newcommand{\K}{K}
\newcommand{\N}{{\cal N}}
\newcommand{\Z}{{\cal Z}}

\date{}
\begin{document}

\maketitle

\begin{abstract}
Many physical theories like
chaos theory are fundamentally concerned with the
conceptual tension between determinism and randomness. 
Kolmogorov complexity can express randomness in determinism
and gives an approach to formulate
chaotic behavior.
\end{abstract}

\section{Introduction}

Ideally, physical theories are abstract representations---mathematical
axiomatic theories for the underlying
physical reality. This reality cannot be directly
experienced, and is therefore unknown and even
in principle unknowable. Instead, scientists postulate
an informal description which is intuitively acceptable,
and subsequently formulate one or more mathematical
theories to describe the phenomena.


{\bf Deterministic Chaos:} Many phenomena in physics (like the weather) satisfy
well accepted deterministic equations. From initial
data we can extrapolate and compute the next states
of the system. Traditionally it was thought that increased
precision of the initial data (measurement) and increased
computing power would result in increasingly accurate
extrapolation (prediction). Unfortunately it turns out
that for many systems this is not the case. In fact,
it turns out that any long range prediction with
any confidence better than what we would get by flipping a fair
coin is practically impossible: this phenomenon is known as chaos
(see \cite{De89} for an introduction). There are two, more or less
related, causes for this:

\begin{description}
\item[Instability]
In certain deterministic systems,
an arbitrary small error in initial conditions can exponentially
increase during the subsequent evolution of the system,
until it encompasses the full range of values achievable
by the system.
This phenomenon of instability of a computation is in fact
well known in numerical analysis: computational procedures
inverting ill-conditioned matrices (with determinant about zero)
will introduce exponentially increasing errors. 
\item[Unpredictability]
Assume we deal with a system described by deterministic equations
which can be finitely represented (like a recursive function).
Even if fixed-length initial segments of the 
infinite binary representation of the real parameters
describing  past states of the system are perfectly known,
and the computational procedure used is perfectly error free,
for many such systems it will still be 
impossible to effectively predict (compute) any
significantly long extrapolation of system states with any confidence
higher than using a random coin flip. This is the 
core of chaotic phenomena: randomness in determinism.
\end{description}

%{\bf Random System States:}
%Classical thermodynamics is concerned with describing
%the physical properties of substances like gases under
%variations of macroscopic observables such as volume,
%temperature and pressure. Certain regularities are
%codified on the basis of experience, and formulated
%as axioms of the theory. Such laws are:
%(i) The total energy of the isolated system is invariant over time;
%and (ii)
%The entropy of an isolated system (in terms of a formula of
%the macroscopic variables)
%does not decrease over time.
%Statistical thermodynamics, also called statistical mechanics,
%tries to derive these classical laws of thermodynamics
%from microscopic phenomena.
%In particular, it is assumed that the underlying reality
%of a physical gas consists of a large number of molecules which
%behave like colliding billiart balls in deterministic Newtonian mechanics,
%but one expresses the entropy of the system as a stochastic notion
%related to unpredictability.
%
%It is considered infeasible to {\em deterministically} analyse
%a system like that consisting of $6.3 \cdot 10^{23}$ (one mole)
%molecules. In contrast, it is considered that the number
%of particles is so large that the overall behavior of the
%system can be approximated by a statistical treatment.
%A {\em stochastic} model is
%formulated where the state of the system is viewed as a random
%variable, and the hard-to-analyze
%deterministic evolution of the system state
%is replaced by an easier-to-analyze stochastic one. 
%In the deterministic system observation shows that it
%strives for an unorganized, random, individual state, like what happens
%when we pour milk in our coffee and stir. The overwhelming majority
%of possible states of the system is of this random type, and they
%cannot significantly be distinguished from one another. In the stochastic  
%treatment one considers the high probability of the system state to
%move to a state in the set of the random individual states, 
%and considers the lack
%of knowledge we have about in which particular state the
%system is, out of the undistinghuishable
%multitude of random states, as increased entropy related to the probabilistic
%ensemble in question. In this way the problem of dealing with
%the propensity of the system to randomize its individual
%state more and more is replaced by the better understood
%phenomenon of stochastic processes striving for a high-entropy mixture.
%Here we have the essence of chaoticity again: the higher the entropy the 
%more unpredictable the system is.
%%Yet the observed phenomena suggest rapid randomization
%%of the individual state. We thus see a fundamental difference
%%between the common probabilistic notion of a random process generating
%%data with certain probabilities, and individual data, some
%%of which are (intuitively) more random than others. How to
%%express the latter phenomena?

%In this model the total
%state of the system of $N$ molecules is a random variable $X$
%consisting of $6N$ parameters, a position $p=(x,y,z)$
%and a impuls momentum vector (mass times velocity vector)
%$m {\bf v}$, ${\bf v} = (v_x , v_y , v_z )$, for each molecule.
%This random variable has outcomes that are mico states
%${\cal S} = \{s_1 , s_2 , \ldots  \}$ each microstate with some
%probability. Considering discrete time,
%at each instant there is a probability associated
%with the transition of $s_i \rightarrow s_j$ defining a Markov chain. 
%With each macroscopic description $D$ of the system there
%corresponds a set of microstates $W \subseteq {\cal S}$.
%The probability that a macrostate $D$
%with less probability concentrated on $W$ changes to a
%macrostate $D'$ with more probability concentrated on associated
%set of microstates $W'$ is larger that vice versa,
%whic corresponds to the entropy of the macrostate rising
%with time with high probability (almost one).
%This phenomenon yields an (almost) deterministic phenomenon
%(the arrow of time) from statistical assumptions

{\bf Probability:}
Classical probability theory deals with randomness in the
sense of {\em random variables}. The concept of random individual
data cannot be expressed. Yet our intuition about the latter is
very strong:
An adversary claims to have a true random coin and invites
us to bet on the outcome. The coin produces a hundred heads
in a row. We say that the coin cannot have been fair. The adversary,
however, appeals to probability theory which says that each sequence
of outcomes of a hundred coin flips is equally likely, $1/2^{100}$,
and one sequence had to come up. 
Probability theory gives us no basis to challenge an outcome
{\em after} it has happened. We could only exclude unfairness
in advance by putting a penalty side-bet on an outcome
of 100 heads. But what about $1010 \ldots$? What about
an initial segment of the binary expansion of $\pi$?

\begin{description}
\item[Regular sequence]
\[ \Pr(00000000000000000000000000) = \frac{1}{2^{26}} \]
\item[Regular sequence]
\[ \Pr(01000110110000010100111001) = \frac{1}{2^{26}} \]
\item[Random sequence]
\[ \Pr(10010011011000111011010000) = \frac{1}{2^{26}} \]
\end{description}

The first sequence is regular, but what is the distinction of
the second sequence and the third? The third sequence was generated
by flipping a quarter. The second sequence is very regular:
$0,1,00,01, \ldots $. The third sequence will pass
(pseudo) randomness tests.

In fact, classical probability theory cannot express
the notion of {\em randomness of an individual sequence}.
It can only express expectation of properties of the
total set of sequences under some distribution.

This is analogous to the situation in physics
above. How can `an individual object be random?'
is as much a probability theory paradox as
`how can an individual sequence
of states of a deterministic system be random?'
is a paradox of deterministic physical systems.

In probability theory the problem has found a satisfactory
resolution by combining notions of computability 
and information theory to express the complexity of a finite object.
This complexity is the length of the shortest
binary program from which the object can be effectively
reconstructed. It may be called the {\em algorithmic
information content} of the object. This quantity turns
out to be an attribute of the object alone, and recursively
invariant. It is the {\em Kolmogorov complexity} of the
object. It turns out that this notion can be brought to bear on the physical
riddles too. 

%E. Borel (1909) has called an
%infinite sequence of zeros and ones `normal' in the scale of two
%if, for each $k$, the frequency of occurrences
%of each block $y$ of length $k$ in the initial segment of length $n$
%goes to limit $2^{-k}$ for $n$ grows unbounded,
%\cite{Kn81}.
%It is known that normality is not sufficient for randomness,
%since Champernowne's sequence 
%\[123456789101112 \ldots\]
%is normal in the scale of ten. On the other hand, 
%it is universally agreed that a random infinite sequence
%must be normal. (If not, then some blocks occur
%more frequent than others, which can be used to
%obtain better than fair odds for prediction.)
%
%While in the infinite
%case one considers limiting values of quantitive properties which hold 
%for each individual sequence of a set of
%probability 1, in the finite case one
%considers the {\em expected} value of quantities 
%over a set of all sequences of a given length.
%
%We would like to obtain statements that {\em individual} random
%finite sequences have such-and-such quantitative properties in
%terms of their length. But as the result of a sequence
%of $n$ fair coin flips, {\em any} sequence of length $n$ can turn up.
%This raises the question which subset of finite sequences
%can be regarded as genuinely random. In \cite{Ma66}
%the viewpoint is taken that finite sequences which satisfy
%all {\em effective} tests for randomness (known and unknown alike),
%are as random as we will ever be able to verify.
%This form of randomness of individual sequences
%turns out to be equivalent to such sequences having 
%maximal Kolmogorov complexity. In the sequel we use `complexity'
%in the sense of `Kolmogorov complexity'.
%
%It can be proved that each high complexity finite binary sequence
%is `normal' in the sense that each binary block of length
%$k$ occurs about equally frequent for $k$ relatively small,
%\cite{LV91}. 
%We prove the
%particular case $k=1$. We quantify the `about'
%and the `relatively small' in this statement. 

\section{Kolmogorov Complexity}

\label{sec.complexity}
To make this paper
self-contained we briefly review notions and properties required.
For details and further properties see the textbook \cite{LV97}.
We identify the natural numbers ${\cal N}$ and the finite binary sequences as
\[( 0, \epsilon ), (1,0), (2,1),(3,00),(4,01), \ldots ,\]
where $\epsilon$ is the empty sequence.
The {\em length} $l(x)$ 
of a natural number $x$ is the number of
bits in the corresponding binary sequence.
For instance, $l( \epsilon ) = 0$.
If $A$ is a set, then $|A|$ denotes the {\em cardinality} of $A$.
%Let $x,y \in {\cal N}$. $x$ is a {\em  prefix} of $y$ if there is a $z$ 
%such that $y = xz$. If $l(z) > 0$ then the prefix is {\em  proper}.
%A set $A \subseteq {\cal N}$ is {\em  prefix-free}
%if no two distinct elements are proper prefixes
%of each other.
Let $\langle . \rangle : {\cal N} \times {\cal N} \ar {\cal N}$ denote a standard
computable bijective `pairing' function. Throughout this paper, we will assume
that $\langle x,y \rangle  = 1^{l(x)}0xy$.

Define $\langle x,y,z \rangle $ by $\langle x, \langle y,z \rangle  \rangle $. 

We need some notions from the theory of algorithms, see \cite{Ro67}.
Let $\phi_1 , \phi_2 , \ldots $ be a standard enumeration of the
partial recursive functions.
%each of which has a binary one-way input tape, a two-way work tape,
%and an output tape. At the start the input tape contains
%an infinite sequence of bits. 
%A Turing machine $T$ computes the function
%$T: {\cal N} \ar {\cal N}$, defined as $T(x) = y$,
%with $x$ is the input on the tape when the machine starts its computation,
%and $y$ is the output on the tape when the machine halts, otherwise $T(x)$
%is undefined.
%is the part of the input $T$
%has scanned by the time it halts, and $y$ is the contents of the output tape
%upon halting. Since the input tape is one-way, the set of inputs
%$A = \{ T(p) < \inf : p \in {\cal N} \}$ is prefix-free.
The (Kolmogorov) {\em  complexity} of $x \in {\cal N}$, given $y$, is defined as

\[ \C(x| y) = \min \{ l(\langle n,z \rangle ): \phi_n (\langle y,z \rangle ) = x \} .\]

This means that $\C(x|y)$ is the {\em minimal} number of bits 
in a description
from which $x$ can be effectively reconstructed, given $y$.
The unconditional complexity is defined as $\C(x)=\C(x| \epsilon )$.

An alternative definition is as follows. Let
\begin{equation}
\label{universal}
 \C_{\psi}(x|y) = \min \{ l(z): \psi (\langle y,z \rangle ) = x \}
\end{equation} 
be the conditional
complexity of $x$ given $y$ with reference to decoding function $\psi$.
Then $\C(x|y) = \C_{\psi}(x|y)$
for a universal partial recursive function $\psi$
that satisfies $\psi (\langle y,n,z \rangle )= \phi_{n} (\langle y,z \rangle )$.

We will also make use of the {\em prefix\/} complexity $\K(x)$, which denotes
the shortest {\em self-delimiting\/} description.
To this end, we consider so called {\em prefix\/} Turing machines,
which have only 0's and 1's on their input tape,
and thus cannot detect the end of the input.
Instead we define an input as that part of the input tape which the machine
has read when it halts. When $x \neq y$ are two such input, we clearly
have that $x$ cannot be a prefix of $y$, and hence the set of inputs forms
what is called a {\em prefix code\/}.
We define $\K(x)$ similarly as above, with reference to a universal
prefix machine that first reads $1^n0$ from the input tape and then
simulates prefix machine $n$ on the rest of the input.

We need the following properties. 
Throughout `$\log$' denotes the binary logarithm.
We often use $O(f(n)) = - O(f(n))$, so that 
$O(f(n))$ may denote a negative quantity.
For each $x,y\in {\cal N}$ we have 
\begin{equation}
\C(x|y) \leq l(x) + O(1).
\label{upperbound}
\end{equation}
For each $y \in {\cal N}$ there is an $x \in {\cal N}$ of length $n$
such that $\C(x|y) \geq n$. In particular, we can set $y = \epsilon$.
Such $x$'s may be called {\em random}, since they are
without regularities that can be used to compress
the description. Intuitively,
the shortest effective description of $x$
is $x$ itself. In general, for each $n$ and $y$, there are at least
$2^n -2^{n-c} +1$ distinct $x$'s of length $n$ with
\begin{equation}
\C(x|y) \geq n-c.
\label{random}
\end{equation}

In some cases we want to encode $x$ in {\em self-delimiting}
form $x'$, in order to be able to decompose $x'y$
into $x$ and $y$. 
Good upper bounds on the prefix complexity of $x$ are obtained by iterating
the simple rule that a self-delimiting (s.d.) description of the length of $x$
followed by $x$ itself is a s.d. description of $x$. 
For example, $x'=1^{l(x)} 0 x$ and $x''=1^{l(l(x))}0l(x)x$ are
both s.d. descriptions for $x$, and this shows
that $\K(x) \leq 2l(x)+O(1)$ and $\K(x) \leq l(x) + 2l(l(x))+ O(1)$.

Similarly, we can encode $x$
in a self-delimiting form of its shortest program $p(x)$
($l(p (x))=\C(x)$) in $2\C(x) + 1$ bits.
Iterating this scheme, we can encode $x$ as
a selfdelimiting program of $\C(x)+2 \log \C(x) +1$ bits, 
which shows that $\K(x) \leq \C(x)+2 \log \C(x) +1$,
and so on.

%Denote $\C(\langle x,y \rangle )$ by $\C(x,y)$. 
%(We also denote $\C(x|\langle y,z \rangle )$ by $\C(x|y,z)$.)
%It can be proved, \cite{Ko83,LV97},
%that, up to an $O( \log \min \{ \C(x),\C(y) \} )$ additive term,
%\begin{equation}
%\C(x,y)=\C(x)+\C(y|x)=\C(y)+\C(x|y) .
%\label{symmetry}
%\end{equation}
%This identity is sometimes referred to as
%{\em symmetry of information}.
%The logarithmic error term is caused by the fact that we need to
%encode a delimitor to separate two concatenated binary sequences
%(description of $x$ and description of $y$ given $x$)
%in the original pair. 

%\subsection{Expectation versus Complexity}
%
%To derive our results,
%we often use a common pattern
%of argument.
%
%Consider the sample space $S=\{0,1\}^{\ast}$
%with uniform probability $\Pr (x)=2^{-2l(x)}$. Put $S^n = \{0,1\}^n$.
%Then, $\Pr (x|x \in S^n ) = 2^{-n}$.
%Let $R:S \ar \Z$, total recursive, be a function that (in our case)
%measures the deviation between some function $g$ of $x$ and a reference value
%$r(l(x))$ for all strings of the same length.
%%, and $r: \N \ar \Z$, also total recursive, a function that
%% gives a {\em reference} value for each $S^n$.
%We are interested in the relation
%between the complexity of a string $x$ and this deviation.
%%  of $R(x)$ from $r(l(x))$.
%A natural choice of $r$ would be the average $g(x)$ over $S^n$.
%Fix a class $D$ of {\em deficiency} functions
%$\defic: \N \ar \N$ for which $K(n|n-\defic(n))=O(1)$.
%This is satisfied by every monotone sublinear recursive function that we
%are interested in.
%The complexity of $R$ can be identified with the complexity of its index
%in the effective enumeration of recursive functions, which we can assume
%equals some constant plus (optionally) the complexity of its parameters.
%
%Define the tail probability
%\[p(R;n,m)= \Pr\{x \in S^n: |R(x)| \geq m \} .\]
%
%\begin{lemma}[Tail Lemma]
%Let $f$ be a function
%from $\N \times \N$ to $\N$ satisfying
%\[ -\log p(R;n,f(n,k)) \geq \K(R|n) + k + O(1). \]
%%Then for any $\defic \in D$, we have that all $x$
%%with $\C(x) > n - \defic(n)$ ($n=l(x)$),
%satisfy \[ |R(x)| < f(n,\defic(n)).\]
%%%\label{tail}
%\end{lemma}
%
%{\em Proof.}  
%By contradiction. Assume that for some $\defic \in D$, there exists
%an $n$ such that $A=\{x \in S^n: |R(x)| \geq f(n,\defic(n)) \}$ is
%non-empty. We can describe such an $x \in A$ in the following way:
%
%\begin{enumerate}
%\item
%let $s$ be a s.d. program for $n$ given $n-\defic(n)$, of length
%$l(s) = K(n|n-\defic(n))=O(1)$.
%\item
%let $q$ be a s.d. program for $R$ given $n$, of length $l(q)=\K(R|n)$.
%\item
%let $i$ be the index of $x$ in an effective enumeration of $A$,
%from the $x$'s with the highest $|R(x)|$'s down.
%%From $|A| = 2^n \Pr(A) = 2^n p(R;n,f(n,\defic(n)))$ it follows that
%the length of the (not necessarily s.d.) description of $i$ satisfies:
%
%\begin{eqnarray*}
%l(i) \leq \log |A| & = & n + \log p(R;n,f(n,\defic(n))) \\
 %& \leq & n -\K(R|n) - \defic(n) - O(1). 
%\end{eqnarray*}
%\end{enumerate}
%
The string $sqi$ has length at most $n - \defic(n) - O(1)$ and can be padded
%to a string $z$ of length exactly $n - \defic(n) - c$, where $c$ is
%a constant determined below. From $z$ we can reconstruct $x$
%by first using its length plus $c$ to compute $n$ (and $\defic(n)$)
%from $s$, then use $n$ to obtain $R$ from $q$, and finally
%enumerate $A$
%to obtain the $i$th element.
%Note that we can enumerate $A$ up to the $i$th element without
%using $f$ at all, since we enumerate from the $x$'s with the
%highest $|R(x)|$ down.
%So, if recursive function $\psi$ embodies above procedure for
%reconstructing $x$, we have, by Equation~\ref{universal},
%\[ \C(x) \leq \C_{\psi}(x) + c_{\psi} \leq n - \defic(n) - c + c_{\psi}. \]
%Choosing $c=c_{\psi}$ finishes the proof.  $\Box$
%
%\begin{cor}[Tail Lemma Dual]
%The exact same argument shows that for sufficiently random
%$x$, the deviation $|R(x)|$ is not too small.
%We thus obtain a Tail Lemma Dual
%starting from $q(R;n,m)= \Pr\{x \in S^n: |R(x)| \leq m \}$.
%\label{dual}
%\end{cor}
%%
%\subsection{Number of Zeros and Ones}

%Let $x$ have length $n$.
%It is known that if $\C(x|n) = n+O(1)$,
%then the number of zeros it contains is, \cite{Ma66},
%\[ \frac{n}{2} + O( \sqrt n ). \]

%\subsection{Fixed Complexity}
%
%\subsection{Fixed Number of Zeros}
%
%It may be surprising at first glance, but there
%are no maximally complex sequences with about equal
%number of zeros and ones. Equal numbers of zeros and ones is
%a form of regularity, and therefore lack of complexity. 
%Using the same notation as before, if $R(x)=O(1)$ then
%the randomness deficiency $\defic(n)=n-\C(x)$ is relatively large.
%For instance,
%
%\begin{eqnarray*}
 %q(R;n,m) & = & \Pr \{x \in S^n: |R(x)| \leq m \} \\
  %& \leq & (2m+1)2^{-n} \chooose{n}{n/2}
 %=  O(\frac{m}{\sqrt{n}}). 
%%\end{eqnarray*}
%
%Thus, setting $f(n,k)=2^{-k-O(1)} \sqrt{n}$, the Tail Law Dual
%(Corollary~\ref{dual}) gives us:
%all $x$ with $\C(x) > n - \defic(n)$ ($n=l(x)$), satisfy
%
%\[ |\#ones(x)- \frac{n}{2} | > 2^{-\defic(n)-O(1)} \sqrt{n}. \]
%
%Perhaps more interestingly, we can 
%define 
%\[R'(x)=\#ones(x)-(\frac{n}{2}+j),\]
%so that $\K(R'|n)$ is about $\K(j)$.
%%Applying the Tail Law Dual with 
%
%\[ f(n,k)=2^{-k-\K(j)-O(1)} \sqrt{n}, \]
%
%we then find that all $x$ with $\C(x) > n - \defic(n)$ satisfy
%
%%\[ |\#ones(x)-( \frac{n}{2} +j)| > 2^{-\defic(n)-\K(j)-O(1)} \sqrt{n}. \]
%%
%%%%%This means that for a random $x$ having exactly $j + n/2$ ones,
%%$\K(j)$ must be at least about $\log n$.

\subsection{Random Sequences}

We would like to call an infinite sequence $\omega \in \{0,1\}^{\infty}$
random if $\C ( \omega_{1:n} ) \geq n - O(1)$ for all $n$.
It turns out that such sequences do not exist. This occasioned
the celebrated theory of randomness of P. Martin-L\"of,
\cite{Ma66}. Later it turned out, \cite{Ch75}, that we can yet precisely
define the Martin-L\"of random sequences, but using
prefix Kolmogorov complexity.
we need.

\begin{theo}
\label{martin.lof}
An infinite binary sequence $\omega$ is random in the sense of Martin-L\"of 
iff there is an $n_0$ such that
$\K( \omega_{1:n} ) \geq n$ for all $n > n_0$,
\end{theo}

That $\omega$ is random in Martin-L\"of's sense means that
it will pass {\em all} effective tests for randomness:
both the tests which are known now and the ones which are
as yet unknown \cite{Ma66}. 

Similar properties hold for high-complexity finite strings,
although in a less absolute sense.

For every finite set $S  \subseteq \{0,1\}^*$ containing
$x$ we have $K(x | S)\le\log|S|+O(1)$.
Indeed, consider the selfdelimiting code of $x$
consisting of its $\lceil\log|S|\rceil$ bit long index
of $x$ in the lexicographical ordering of $S$.
This code is called
\emph{data-to-model code}.
The lack of typicality
of $x$ with respect to $S$
is the amount by which $K(x|S)$
falls short of the length of the data-to-model code.
The {\em randomness deficiency} of $x$ in $S$ is defined by
      \begin{equation}\label{eq:randomness-deficiency}
\delta (x | S) = \log |S| - K(x | S),
      \end{equation}
for $x \in S$, and $\infty$ otherwise.
If $\delta(x | S)$ is small, then $x$ may be considered
as a {\em typical} member
of $S$. 
There are no simple special properties that
single it out from the majority of elements in $S$.
This is not just terminology: If $\delta (x | S)$ is small, then $x$
satisfies {\em all} properties of low Kolmogorov complexity
that hold with high probability for the elements of $S$. For example:
Consider strings $x$ of length $n$ and let $S = \{0,1\}^n$ be a set of such
strings. Then $\delta (x | S) = n - K(x |ni \pm O(1)$.

(i) If $P$ is a property satisfied by all $x$ with
$\delta(x | S) \le \delta (n)$,
then $P$ holds with probability at
least $1-1/2^{\delta(n)}$ for the elements of $S$.

(ii) Let
$P$ be any
property
that holds with probability at least
$1-1/2^{\delta (n)}$ for the
elements of $S$. Then, every such $P$ holds
simultaneously for every $x \in S$
with $\delta (x | S)\le\delta (n)-K(P|n)-O(1)$.





\section{Algorithmic Chaos Theory}

For convenience assume that time is discrete: ${\cal N}$.
In a deterministic system $X$ the 
{\em state} of the system at time $t$ is $X_t$.
The {\em orbit} of the system is the sequence of subsequent states
 $X_0 , X_1 , X_2 , \ldots$. For convenience we assume
the states are elements of $\{0,1\}$. The definitions below
are easily generalized. For each system, be it deterministic
or random, we associate a measure $\mu$ with the space
$\{0,1\}^{\infty}$ of orbits. That is, $\mu (x)$
is the probability that an orbit starts with $x \in \{0,1 \}^*$.

Given an initial segment $X_{0:t}$ of the orbit we want
to compute $X_{t+1}$. Even if it would not be possible
to compute $X_{t+1}$, we would like to compute a 
prediction of it which does better than a random coin flip.

\begin{definition}\label{def.chaos}
\rm
Let the set of orbits be $S= \{0,1\}^{\infty}$
with the Lebesgue measure $\lambda$.
Let $\phi$ be a partial recursive function and 
let $\omega \in S$. Define
\[ \zeta_i = \left\{ \begin{array}{ll}
1 & \mbox{if $\phi ( \omega_{1:i-1} ) = \omega_i$} \\
0 & \mbox{otherwise}
\end{array}
\right. \]
A deterministic system is {\em chaotic} if, for every
computable function $\phi$, we have
\[ \lim_{t \rightarrow \infty} \sum_{i=0}^{t-1} \zeta_i 
 = \frac{1}{2} ,\]
with probability 1.
\end{definition}

A well-known example of a chaotic system is the {\em doubling map},
\cite{Fo83}. 
Consider the {\it deterministic} system $X$ with initial state
$X_0 = 0. \omega$ a real number in the interval $[0,1]$
where $\omega \in S$ is the binary representation. 
\begin{equation}\label{ford.1}
X_{n+1} = 2X_n \pmod{1} 
\end{equation}
where $\pmod{1}$ means drop the integer part. Thus, all iterates of
equation~\ref{ford.1} lie in the unit interval $[0,1]$. In physics,
this is called the `energy surface' of the orbit.
We can partition this energy surface into
two cells, a left cell $[0, \frac{1}{2} )$ and a right cell
$[\frac{1}{2} , 1]$. Thus $X_n$ lies in the left cell
if and only if the $n$th digit of $\omega$ is 0.


One way to derive the doubling map is as follows:
In chaos theory, \cite{De89}, people have for
years being studying the discrete logistic equation
\[ Y_{n+1} = \alpha Y_n (1 - Y_n ) \]
which maps the unit interval upon itself when $0 \leq \alpha \leq 4$.
When $\alpha =4$, setting $Y_n = \sin^2 \pi X_n$,
we obtain:
\[ X_{n+1} = 2 X_n \pmod{1} . \]

\begin{lemma}
There are a chaotic systems (like $X$ and $Y$ above).
\end{lemma}
\begin{proof}
We prove that $X$ is a chaotic system. Since $Y$ reduces to $X$
by specialization,this shows that $Y$ is chaotic as well.
Assume $\omega$ is random. Then by Theorem~\ref{martin.lof}, 
\begin{equation}\label{eq.omega.random}
C( \omega_{1:n} ) > n- 2 \log n +O(1).
\end{equation}
Let $\phi$ be any partial recursive function.
Construct $\zeta$ from $\phi$ and $\omega$ as in Definition~\ref{def.chaos.finite}.

Assume by way of contradiction that there is an $\epsilon > 0$ such that
\[ | \frac{1}{n} \lim_{n \rightarrow \infty} 
\sum_{i=1}^n \zeta_i - \frac{1}{2} | \geq \epsilon . \]
Then,
there is a $\delta > 0$ such that
\begin{equation}\label{eq.zeta.compl}
\lim_{n \rightarrow \infty} \frac{C( \zeta_{1:n} )}{n} \leq (1- \delta ) . 
\end{equation}

We prove this as follows. The number of binary sequences of length $n$
where the numbers of 0's and 1's differ by at least an $\epsilon n$ 
is 
\[ N = 2 \cdot 2^n \sum_{m = ( \half + \epsilon)n}^n b(n, m, \half )\]
where $b(n,m,p)$
is the probability of $m$ successes out of $n$ trials in a
$( p , 1-p )$ Bernoulli process: the Binomial distribution.
A general estimate of the tail probability of the binomial distribution,
with $m$ the number of successful outcomes in $n$ experiments
with probability of success $0 < p < 1$ and $q=1-p$, 
is given by Chernoff's
bounds, \cite{ES74,CLR90},
\begin{equation}
\Pr (|m -np| \geq \epsilon n ) \leq 2e^{- ( \epsilon n)^2 /3n } .
\label{chernoff}
\end{equation}
Therefore, we can describe any element $\zeta_{1:n}$
concerned by giving
$n$ and $\epsilon n$ in $2 \log n + 4 \log \log n$ bits selfdelimiting
descriptions, and pointing out the string concerned
in a constrained ensemble of at most $N$ elements in $\log N$ bits.
Therefore,
\[ C(\zeta_{1:n}) \leq n - \epsilon^2 n \log e + 2 \log n +
4 \log \log n + O(1) . \]
That is, we can choose
\[ \delta = \epsilon^2 \log e + 
\frac{2 \log n + 4 \log \log n + O(1)}{n} . \]
Next, given $\zeta$ and $\phi$ we can reconstruct $\omega$
as follows: 


\tt 
for $i := 1,2, \ldots$ do: \\
	if $\phi ( \omega_{1:i-1} ) = a$ and $\zeta_i = 0$ then
	$\omega_i := \neg a$ \\
	else $\omega_i := a$.
\rm


Therefore,
\begin{equation}\label{eq.omega.compl}
C( \omega_{1:n} ) \leq C( \zeta_{1:n} ) + K ( \phi ) + O(1) .
\end{equation}
Now Equations~\ref{eq.omega.random}, \ref{eq.zeta.compl},
\ref{eq.omega.compl} give the desired contradiction.
By Theorem~\ref{martin.lof}, the set of $\omega$'s satisfying
Equation~\ref{eq.omega.random} has uniform measure one,
which proves the lemma.
\end{proof}

 In \cite{Fo83} the argument is as follows.
 Assuming that the initial state is randomly drawn from $[0,1)$
 according to the uniform measure $\lambda$, we can use 
complexity arguments to show that the doubling map's observable
 orbit cannot be predicted better than a coin toss.
 Namely, with $\lambda$-probability 1 the drawn
 initial state will be a Martin-L\"of random
 infinite sequence. Such sequences
 by definition cannot be effectively predicted
 better than
 a random coin toss, see \cite{Ma66}.

 But in this case we do not need to go
 to such trouble. The observed orbit essentially
 consists of the consecutive bits of the initial state.% Selecting that initial state randomly from the
 uniform measure is isomorphic to flipping a fair
 coin to generate it. This raises the challenging problem
 of a meaningful application of Kolmogorov complexity
 to chaos problems.

From a practical viewpoint it may be argued that we really
are not interested in infinite sequences: in practice
the input will always be finite precision. Now an infinite
sequence which is random may still have an arbitrary long finite
initial segment which is completely regular. Therefore,
we analyse the theory for finite precision inputs in the
following section. 

\subsection{Chaos with Finite Precision Input}

In the case of infinite precision real inputs, the distinction
between chaotic and non-chaotic systems can be precisely
drawn. In the case of finite precision inputs the distinction
is necessarily a matter of degree. This occasions
the following definition.


\begin{definition}\label{def.chaos.finite}
\rm
Let $S, \lambda , \phi , \omega$ and 
$\zeta$ be as in Definition~\ref{def.chaos}.
A deterministic system with {\em input
precision} $n$ is $( \epsilon , \delta )$-{\em chaotic} if, 
for every
computable function $\phi$, we have
\[ |\sum_{i=1}^{n} \zeta_i 
 - \frac{1}{2} | \geq \epsilon ,\]
with probability at least $1- \delta$.
\end{definition}

So systems are chaotic in the sense
of Definition~\ref{def.chaos}, like the doubling map above,
iff they are $(0,0)$-chaotic with precision $\infty$.
The system is {\em probably approximately inpredictable}:
a {\em pai}-chaotic system.

%Next, we consider the notion of {\em computational feasibility}.
%It is universaly agreed in the theory of computation to
%consider a procedure as intuitively feasible if 
%it can be deterministically executed in
%polynomial time. It is useful to apply this criterion to chaoticity
%as well.
%
%\begin{definition}
%\rm
%A deterministic system with input
%precision $n$ is {\em polynomially chaotic} if
%it is $( \epsilon , \delta )$-chaotic 
%for every
%function $\phi$ which can be computed 
%in $p(n, 1/ \epsilon , 1/ \delta )$ time, 
%where $p$ is a polynomial.
%\end{definition}

\begin{theo}
Systems $X$ and $Y$ above are $( \sqrt{ (\delta (n) + O(1)) \ln 2 /n},
1/2^{\delta (n)}$-chaotic for every function $\delta$ such that
$0 < \delta(n) < n$ .

\end{theo}

\begin{proof}
We prove that $X$ is $(\epsilon, \delta)$-chaotic. Since $Y$ reduces to $X$,
this implies that $Y$ is $(\epsilon, \delta)$-chaotic as well.

Assume that $x$ is a binary string of length $n$ with
\begin{equation}\label{eq.random.x}
C(x) \geq n- \delta (n) .
\end{equation}
Let $\phi$ be a polynomial time computable function, and define $z$ by:
\[ z_i = \left\{ \begin{array}{ll}
1 & \mbox{if $\phi ( x_{1:i-1} ) = x_i$} \\
0 & \mbox{otherwise}
\end{array}
\right. \]

Then, $x$ can be reconstructed from $z$ and $\phi$ as before,
and therefore:
\[ C(x) \leq C(z) + K( \phi ) + O(1) . \]
By Equation~\ref{eq.random.x} this means

\begin{equation}\label{eq.char.z}
C(z) \geq n - \delta (n) - K( \phi ) + O(1) . 
\end{equation}

We analyse the number of zeros and ones in $z$.
Using Chernoff's bounds,  Equation~\ref{chernoff},
with 
$p=q= \frac{1}{2}$,
the number of $z$'s which have an excess of $\epsilon n$
of ones over zeros is:

\[ N \leq 2^{n+1}e^{- ( \epsilon n )^2 / n } \]

with
\[ |\#ones(x)- \frac{n}{2} | < \epsilon n .\]

Then, we can give an effective description of $z$ by giving a description of
$\phi$, $\delta$ and $z$'s index in the set of size $N$
in this many bits
\begin{equation}
\label{eq.descr.z}
 n - \epsilon^2 n \log e + K( \phi ) + K ( \delta ) + 
2 \log  K( \phi ) K ( \delta ) + O(1).
\end{equation}

From Equations~\ref{eq.char.z}, \ref{eq.descr.z} we find 
\begin{equation}
\epsilon \leq \frac{ \sqrt{ \delta (n) + 2K( \phi )
+ K( \delta ) + 2 \log K( \phi ) K ( \delta ) + O(1)}}{n \log e}
\end{equation}

Making the simplifying assumption that $K( \phi ), K( \delta ) = O(1)$
this yields
\begin{equation}\label{result1}
 |\#ones(z)- \frac{n}{2} | < \sqrt{ ( \delta (n) + O(1))n \ln 2 }
\end{equation}


The number of binary strings $x$ of length $n$ with
$C(x) < n - \delta (n)$ is at most $2^{n- \delta (n)} -1$
(there are not more programs of length less than $n- \delta (n)$).
Therefore, the uniform probability of a real number starting
with an $n$-length initial segment $x$ such that $C(x) \geq n - \delta (n)$
is given by: 

\begin{equation}\label{eq.prob}
\lambda \{ \omega : C( \omega_{1:n} \geq n - \delta (n) \}
> 1 - \frac{1}{2^{\delta (n)}} . 
\end{equation}

Therefore, system $X$ is $( \epsilon , \delta )$ chaotic
with $\epsilon = \sqrt{ (\delta (n) + O(1)) \ln 2 /n}$
and $\delta = 1/2^{\delta (n)}$.
% which means it
%is polynomially chaotic as long as 
%$\delta (n) = \Omega (1)$ and $2^{\delta (n)}$ is polynomial in $n$,
%for all $\phi$ which can be
%computed in $p( 1/ \epsilon , 1/ \delta , n )$ time, with $p$
%a polynomial.

\end{proof}


\begin{thebibliography}{9}

\bibitem{Ch75}
G.J. Chaitin, A theory of program size formally identical
to information theory, {\em J. Assoc. Comp. Mach.},
{\bf 22}(1975), 329-340.

\bibitem{CLR90}
Corman, C. Leiserson, R. Rivest,
{\em Introduction to Algorithms}, 1990.

\bibitem{De89}
R.L. Devaney, An Introduction to Chaos Dynamical Systems, Addison-Wesley,
2nd Edition, 1989.

\bibitem{ES74}
P. Erd\"{o}s and J. Spencer,
{\em  Probabilistic Methods in Combinatorics},
Academic Press, New York, 1974.

\bibitem{Fo83}
J. Ford, How random is a random coin toss? {\em Physics Today},
36(1983), April, 40--47. 

\bibitem{Ga74}
P. G\'{a}cs, On the symmetry of algorithmic information,
{\em Soviet Math. Dokl.}, 
{\bf 15}(1974), 1477-1480.

\bibitem{GKP89}
R.L. Graham, D.E. Knuth, O. Patashnik,
{\em Concrete Mathematics},
Addison-Wesley, 1989.

%\bibitem{Fo83}
%J. Ford, `How random is a random coin toss?',
%{\em Physics Today}, Series A, 1983.

\bibitem{Kn81}
D.E. Knuth, {\em Seminumerical Algorithms}, Addison-Wesley, 1981.

\bibitem{Ko65}
A.N. Kolmogorov,
Three approaches to the definition of the concept `quantity
of information', {\em  Problems in Information Transmission},
{\bf 1:1}(1965), 1-7.

\bibitem{Ko83}
A.N. Kolmogorov, Combinatorial foundation of information theory
and the calculus of probabilities,
{\em Russian Math. Surveys}, {\bf 38:4}(1983), 29-40.

\bibitem{Le74}
L.A. Levin,
Laws of Information conservation (non-growth) and aspects of the foundation
of probability theory, {\em Problems in Information Transmission},
{\bf 10}(1974), 206-210.

\bibitem{LV97}
M. Li and P.M.B. Vit\'{a}nyi,
\it An Introduction to Kolmogorov Complexity
and its Applications%
\rm , Second Edition, Springer-Verlag, New York, 1997.

\bibitem{LV91}
M. Li and P.M.B. Vit\'{a}nyi,
Kolmogorov complexity arguments in
Combinatorics, {\em J. Comb. Th., Series A}, 66:2(1994), 226-236.
Correction, {\em Ibid.}, 69(1995), 183.

\bibitem{Ma66}
P. Martin-L\"{o}f, On the definition of random sequences,
{\em Information and Control}, (1966).

\bibitem{Ro67}
H.J. Rogers, Jr., {\em Theory of Recursive Functions 
and Effective Computability}, McGraw-Hill, 1967.

\bibitem{Sh48}
C.E. Shannon, A mathematical theory of communication,
{\em Bell System Tech. J.}, {\bf 27}(1948), 379-423, 623-656.

\end{thebibliography}
\end{document}



nlin0303016.extracted_bib
\begin{thebibliography}{9}

\bibitem{Ch75}
G.J. Chaitin, A theory of program size formally identical
to information theory, {\em J. Assoc. Comp. Mach.},
{\bf 22}(1975), 329-340.

\bibitem{CLR90}
Corman, C. Leiserson, R. Rivest,
{\em Introduction to Algorithms}, 1990.

\bibitem{De89}
R.L. Devaney, An Introduction to Chaos Dynamical Systems, Addison-Wesley,
2nd Edition, 1989.

\bibitem{ES74}
P. Erd\"{o}s and J. Spencer,
{\em  Probabilistic Methods in Combinatorics},
Academic Press, New York, 1974.

\bibitem{Fo83}
J. Ford, How random is a random coin toss? {\em Physics Today},
36(1983), April, 40--47. 

\bibitem{Ga74}
P. G\'{a}cs, On the symmetry of algorithmic information,
{\em Soviet Math. Dokl.}, 
{\bf 15}(1974), 1477-1480.

\bibitem{GKP89}
R.L. Graham, D.E. Knuth, O. Patashnik,
{\em Concrete Mathematics},
Addison-Wesley, 1989.

%\bibitem{Fo83}
%J. Ford, `How random is a random coin toss?',
%{\em Physics Today}, Series A, 1983.

\bibitem{Kn81}
D.E. Knuth, {\em Seminumerical Algorithms}, Addison-Wesley, 1981.

\bibitem{Ko65}
A.N. Kolmogorov,
Three approaches to the definition of the concept `quantity
of information', {\em  Problems in Information Transmission},
{\bf 1:1}(1965), 1-7.

\bibitem{Ko83}
A.N. Kolmogorov, Combinatorial foundation of information theory
and the calculus of probabilities,
{\em Russian Math. Surveys}, {\bf 38:4}(1983), 29-40.

\bibitem{Le74}
L.A. Levin,
Laws of Information conservation (non-growth) and aspects of the foundation
of probability theory, {\em Problems in Information Transmission},
{\bf 10}(1974), 206-210.

\bibitem{LV97}
M. Li and P.M.B. Vit\'{a}nyi,
\it An Introduction to Kolmogorov Complexity
and its Applications%
\rm , Second Edition, Springer-Verlag, New York, 1997.

\bibitem{LV91}
M. Li and P.M.B. Vit\'{a}nyi,
Kolmogorov complexity arguments in
Combinatorics, {\em J. Comb. Th., Series A}, 66:2(1994), 226-236.
Correction, {\em Ibid.}, 69(1995), 183.

\bibitem{Ma66}
P. Martin-L\"{o}f, On the definition of random sequences,
{\em Information and Control}, (1966).

\bibitem{Ro67}
H.J. Rogers, Jr., {\em Theory of Recursive Functions 
and Effective Computability}, McGraw-Hill, 1967.

\bibitem{Sh48}
C.E. Shannon, A mathematical theory of communication,
{\em Bell System Tech. J.}, {\bf 27}(1948), 379-423, 623-656.

\end{thebibliography}