\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs}
\usepackage{geometry}
\geometry{margin=1in}
\usepackage{enumitem}
\setlength{\parskip}{2pt}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem*{remark}{Remark}
\newtheorem*{remarks}{Remarks}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\renewcommand{\thesection}{\S\arabic{section}}
\renewcommand{\thetheorem}{\arabic{section}.\arabic{theorem}}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zp}{\mathbb{Z}^{+}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rp}{\mathbb{R}^{+}}
\newcommand{\co}{\mathfrak{A}}
\newcommand{\cL}{\mathscr{L}}
\newcommand{\AL}{\Lambda_{\cL}}
\newcommand{\fM}{\mathfrak{M}}
\newcommand{\card}{\operatorname{card}}
\renewcommand{\phi}{\varphi}

\title{Entropy and the Complexity of Trajectories\\ of a Dynamical System}
\author{A.~A.~Brudno}
\date{}

\begin{document}
\maketitle

\begin{center}
\textit{Dedicated to the memory of\\ V.~M.~Alekseev}
\end{center}

\medskip

\noindent\textit{Trudy Moskovskogo Matematicheskogo Obshchestva,} 1982, Vol.~44.\quad UDC 513.88

\tableofcontents

\section*{Introduction}

\subsection*{1.~Statement of the problem}

The classical theory of dynamical systems (DS) has usually been concerned with \emph{flows}, that is, systems with continuous time. However, since Poincar\'e it has been well known that it is generally sufficient to confine oneself to the study of systems with discrete time, i.e.\ not flows but \emph{mappings}. Accordingly, by a DS $(X,T)$ in this paper we mean one of two objects:
\begin{enumerate}
  \item A continuous mapping $T\colon X\to X$ of a compact topological space $X$ into itself (a \emph{topological} DS).
  \item A single-valued mapping $T\colon X\to X$ of a space $X$ equipped with a $\sigma$-algebra of measurable sets, measurable with respect to that $\sigma$-algebra (a \emph{metric} DS).
\end{enumerate}

Interest in the problems of the theory of dynamical systems, especially heightened in the last 10--20 years, has been stimulated by the fact that the results and methods of this theory find direct application in problems of classical mechanics, statistical physics, and in a number of applied disciplines (in particular, in information theory). At present the consideration of various characteristics of a dynamical system associated with the concept of \emph{entropy} introduced by A.~N.~Kolmogorov \cite{10} is especially popular. This entropy is called \emph{metric}; the authors of \cite{18} introduced the notion of \emph{topological} entropy.

Many facts of the entropy aspect of the theory of dynamical systems allow one to regard the entropy of a dynamical system as a certain measure of its complexity.

On the other hand, every dynamical system consists of individual trajectories of generally different nature and complexity. For example, trajectories may be periodic and wandering, recurrent, regular, and so on. It is intuitively clear that the global complexity of the system (i.e.\ its entropy) should be related in some way to the complexity of its individual trajectories.

In order to give precise meaning to this assertion, one must first of all give a mathematically rigorous definition of the notion of ``complexity of a trajectory''.

In the present paper\footnote{A brief presentation of some results of the present paper in somewhat different notation is contained in the note \cite{5}.} such a definition is based, on the one hand, on the ideas of the method of \emph{symbolic dynamics} (a classical method going back to Hadamard and Morse), and, on the other hand, makes use of the concept of \emph{algorithmic complexity of a finite object} introduced by A.~N.~Kolmogorov in his paper \cite{10} devoted to a new foundation of probability theory and information theory.

Using a combination of these two notions, one associates with every trajectory of a topological dynamical system a nonnegative real number $K(x,T)$ characterizing the degree of complexity of the behavior of this trajectory in the phase space of the system.

\subsection*{2.~The main results of the paper}

The main results of the paper consist in establishing connections between the introduced notion of complexity of a trajectory and such traditional notions of the theory of dynamical systems as metric and topological entropy, decomposition into ergodic sets, and others. In particular, the following theorems are proved in the paper:

\medskip\noindent\textbf{Theorem 3.1.} \emph{For every ergodic measure $\mu$,
\[
K(x,T)=h_{\mu}(T)
\]
for $\mu$-almost all $x\in X$.}

\medskip\noindent\textbf{Theorem 3.2.} \emph{For every point $x\in X$,
\[
K(x,T)\le h_T(x).
\]}

Here $h_{\mu}(T)$ is the metric entropy (with respect to the measure $\mu$) of the DS $(X,T)$, and $h_T(x)$ is the entropy of a point in the sense of Kamae \cite{24} (that is, $h_T(x)=\sup_{\mu\in V_T(x)} h_{\mu}(T)$, where $V_T(x)$ is the set of individual measures corresponding to the point $x$ in the framework of the Krylov--Bogolyubov theory).

In particular, by Theorem~3.2 the complexity of any trajectory does not exceed the topological entropy of the system.

\subsection*{3.~Historical survey}

We briefly dwell on results bearing in some degree on our subject. Apparently the first problem of this kind arose in information theory, and the first result in this direction was Shannon's result on the complexity of coding messages of a discrete ergodic source. However, Shannon's results, like several others, were essentially incomplete, primarily because of the absence of a mathematically rigorous definition of the notion of ``complexity of a message''. Such a definition was given, as already mentioned, in the language of algorithm theory by A.~N.~Kolmogorov in 1965. The survey paper \cite{7} gives many examples showing the fruitfulness of considering Kolmogorov-type complexity characteristics for probability theory and information theory. In addition, that paper contains several assertions relating entropy and complexity characteristics within those disciplines. In particular, the method of proof of Theorem~5.1 of \cite{7}, due to A.~N.~Kolmogorov, is essentially used in our paper, and an assertion of L.~A.~Levin announced in \cite{7} served as one of the stimuli for the appearance of the present paper, and can be interpreted as a special case of the situation occurring for metric DS of general type considered in \cite{5}.

As for the theory of dynamical systems itself, in it the study of various characteristics and properties of individual trajectories has always been extremely popular. It suffices to mention such classical theorems as the Poincar\'e--Carath\'eodory theorem on recurrence, the Birkhoff--Khinchin ergodic theorem, the Shannon--McMillan--Breiman theorem, and others. By now a certain number of characteristics of an individual trajectory have accumulated, connected in one way or another with the complexity of behavior of that trajectory in the phase space of the system. A comparative analysis of these characteristics is given in \S 4 of the present paper, where, in particular, the question of the connection of complexity of a trajectory with the notion of randomness in the sense of Martin-L\"of, generally accepted at present, is examined.

In conclusion I consider it my duty to express my deep gratitude to \fbox{V.~M.~Alekseev} under whose direction this work was carried out. I am also grateful to E.~I.~Dinaburg, Ya.~G.~Sinai, A.~M.~St\"epin, A.~T.~Tagi-Zade and M.~V.~Yakobson for useful remarks.

\section*{\S0. Basic concepts and facts used in the paper}
\addcontentsline{toc}{section}{\S0. Basic concepts and facts used in the paper}
\setcounter{section}{0}
\setcounter{theorem}{0}

\subsection*{1}

Both in the metric and in the topological case, the space $X$ is assumed to be equipped with a $\sigma$-algebra $\fM$ consisting of measurable (respectively Borel) sets, invariant under the transformation $T$. In the set $M(X)$ of all normalized measures defined on the $\sigma$-algebra $\fM$ we denote by $M(X,T)$ and $EM(X,T)$ the subsets formed by the invariant and the ergodic measures of the DS $(X,T)$. Following \cite{12}, we shall call a set $A\in\fM$ a \emph{set of invariant measure zero} if $\mu(A)=0$ for every $\mu\in M(X,T)$.

A quadruple $(X,\fM,T,\mu)$ with $\mu\in M(X,T)$ defines a dynamical system in the sense of ergodic theory.

At present there is a known number of survey papers devoted to the entropy aspect of the theory of dynamical systems; the terminology and notation are well established. We therefore find it possible to omit the definitions and description of the basic properties of the familiar entropy characteristics (we follow \cite{20}, without specific references), and to touch only briefly on the method of symbolic dynamics. The main attention will be devoted to questions related to the consideration of the notion of algorithmic complexity in the sense of Kolmogorov, relatively recently introduced and not traditional for the theory of DS.

Let $\co=\{A_i\}_{i\in\cL}$ be a covering of the space $X$, and
\[
\AL = \cL^{\Zp} = \{\omega=\{\omega(i)\}_{i\in\Zp}:\ \omega(i)\in\cL\ \text{for all}\ i\in\Zp\}.
\]
The shift transformation $\sigma\colon\AL\to\AL$ is defined by
\[
\widetilde{\omega}=\sigma(\omega)\iff \widetilde{\omega}(i)=\omega(i+1)\ \text{for all}\ i\in\Zp.
\]
The mapping $\phi_{\co}\colon X\to\AL$ is constructed as follows:
\[
\omega=\{\omega(i)\}_{i\in\Zp}\in\phi_{\co}(x)\iff T^{i}x\in A_{\omega(i)}\ \text{for all}\ i\in\Zp.
\]

The method of symbolic dynamics in the above or somewhat different form has been used by many authors; in particular it is set out in detail in the monograph of V.~M.~Alekseev \cite{1}. In particular, $\sigma(\Omega_{\co})\subseteq\Omega_{\co}$, where $\Omega_{\co}$ is the image of the space $X$ under the mapping $\phi_{\co}$, i.e.
\[
\Omega_{\co}=\Bigl\{\omega\in\AL:\ \bigcap_{i\in\Zp} T^{-i}A_{\omega(i)}\ne\varnothing\Bigr\}.
\]

The DS $(\Omega_{\co},\sigma)$ is called the \emph{symbolic model} of the DS $(X,T)$ corresponding to the cover $\co$. A pair $(\Omega,\sigma)$, where $\Omega$ is an arbitrary invariant Borel\footnote{It is assumed that $\AL$ is equipped with the Tikhonov topology.} subset of $\AL$, is called a \emph{symbolic dynamical system}. In what follows we shall consider not only elements $\omega\in\Omega$ but also their finite segments, putting by definition:
\begin{align*}
\omega^{\langle K,N\rangle} &= \{\omega(i)\}_{i=K}^{N-1} = \omega(K)\omega(K+1)\ldots\omega(N-1);\\
\omega^{N} &= \omega^{\langle 0,N\rangle};\\
\Omega^{N} &= \{\omega^{N}:\ \omega\in\Omega\}.
\end{align*}

In addition, we denote by
\[
C(\omega^{\langle K,N\rangle}) = \{\widetilde{\omega}=\{\widetilde{\omega}(i)\}_{i\in\Zp}:\ \widetilde{\omega}(i)=\omega(i)\ \text{for}\ K\le i\le N-1\}
\]
the \emph{cylinders} in the space $\AL$.

If a partition\footnote{A cover $\co=\{A_i\}_{i\in\cL}$ is called a \emph{partition} if $A_i\cap A_j=\varnothing$ for all $i\ne j$.} $\beta=\{B_i\}_{i\in\cL}$ is measurable, then the additive function $\widetilde{\mu}$ defined on the family of cylinders
\[
\{C(\omega^{\langle K,N\rangle}):\ \omega\in\AL;\ K,N\in\Zp,\ K<N\}
\]
by
\[
\widetilde{\mu}(C(\omega^{\langle K,N\rangle}))=\mu\Bigl(\bigcap_{i=K}^{N-1} T^{-i}A_{\omega(i)}\Bigr)
\]
can be extended (by the classical Kolmogorov theorem) to a measure $\widetilde{\mu}_{\beta}$ on the space $\AL$. Moreover, if $\mu\in M(X,T)$ ($\mu\in EM(X,T)$), then $\widetilde{\mu}_{\beta}\in M(\AL,\sigma)$ ($\widetilde{\mu}_{\beta}\in EM(\AL,\sigma)$).

\subsection*{2}

We now turn to the description of the notion of \emph{algorithmic complexity} of a finite object. Let $A$ be a computable function (algorithm) defined on some subset of the space of all finite words (programs) over the alphabet $\{0,1\}$ and taking values in the set of finite words over some finite alphabet $\cL$. We denote by $l(p)$ the length of a word $p$, i.e.\ the number of letters in it. The complexity $K_{A}(s)$ of a word $s$ with respect to the function $A$ is defined by
\[
K_{A}(s)=\begin{cases}\inf_{p:\,A(p)=s} l(p), & \\ \infty, & \text{if}\ A(p)\ne s\ \text{for all}\ p.\end{cases}
\]
In \cite{10} it is shown that there exists a computable function $B$ such that for any other computable function $A$ and any word $s$,
\[
K_{B}(s)\le K_{A}(s)+C_{A},
\]
where $C_{A}$ is a constant depending on $A$ (but not on $s$).

Such a function $B$ will be called \emph{asymptotically optimal} (a.\,opt.\,f.). In the same paper it is proposed to fix one such function and denote complexity with respect to it simply by $K(s)$.

In the present paper an analogous characteristic is considered for words of infinite length (sequences).

\begin{definition}
The \emph{complexity} of a sequence $\omega=\{\omega(i)\}_{i\in\Zp}$ is the number
\[
K(\omega)=\limsup_{n\to\infty}\frac{K(\omega^{n})}{n}.
\]
\end{definition}

The following simple but technically important statement follows directly from this definition.

\begin{proposition}
For any computable function $A$ and any infinite word $\omega$,
\[
K(\omega)\le K_{A}(\omega);
\]
moreover, if $A$ is an a.\,opt.\,f., then equality holds.
\end{proposition}

In what follows we shall often use the natural correspondence between words over the alphabet $\{0,1\}$ and integers that arises from the binary representation of the latter. Thus, for example,
\[
0\leftrightarrow 0,\quad 1\leftrightarrow 1,\quad 2\leftrightarrow 10,\quad 3\leftrightarrow 11,\ \ldots
\]
If $p=p(1)p(2)\ldots p(k)$ and $q=q(1)q(2)\ldots q(l)$ are words, then by $pq$ and $\bar p$ we denote respectively the words
\begin{align*}
pq &= p(1)\ldots p(k)q(1)\ldots q(l),\\
\bar p &= p(1)p(1)\ldots p(k)p(k)\,01.
\end{align*}
The latter notation will help us in the sequel to distinguish the words $p$ and $q$ separately within the word $\bar p q$.

The following simple relations hold:
\begin{align*}
l(pq) &= l(p)+l(q);\\
l(\bar p) &= 2l(p)+2;\\
\card\{p:l(p)=n\} &= 2^{n};\\
\card\{p:l(p)\le r\} &\le 2^{[r]+1}.
\end{align*}
Here and below, $[r]$ denotes the integer part of the number $r$.

\section{Symbolic dynamical systems}

Throughout this section we shall consider symbolic DS $(\Omega,\sigma)$, with the alphabet $\cL$ ($\Omega\subseteq\AL$) assumed to be finite. Our main goal is the proof of the following theorem.

\begin{theorem}
If $\mu\in EM(\Omega,\sigma)$, then
\[
K(\omega)=h_{\mu}(\sigma)
\]
for $\mu$-almost all $\omega\in\Omega$.
\end{theorem}

The proof of this theorem breaks up into a series of successive lemmas. The first of them is well known.

\begin{lemma}
If $\cL=\{1,2,\ldots,k\}$, $A_{i}=\{\omega:\omega(0)=i\}$ and $\co=\{A_{1},A_{2},\ldots,A_{k}\}$, then $h_{\mu}(\sigma\mid\Omega)=h_{\mu}(\sigma,\co\mid\Omega)$ for any measure $\mu\in M(\Omega,\sigma)$.

Analogously, if $(\Omega,\sigma)$ is a topological DS, then
\[
h(\sigma\mid\Omega)=h(\sigma,\co\mid\Omega).
\]
\end{lemma}

\begin{lemma}
If $\widetilde{\omega}=\sigma^{k}\omega$ for some $k\in\Zp$, then $K(\widetilde{\omega})=K(\omega)$.
\end{lemma}

\begin{proof}
Let $A$ be an arbitrary a.\,opt.\,f. Define a computable function $A'=A'(p)$ whose value on words of the form $p=\bar p_1 \bar p_2 p_3$ is obtained in three stages:
\begin{enumerate}[label=\arabic*.]
  \item Write out the word $A(p_3)$.
  \item Interpret the word $p_2$ as the number of symbols on the left that must be discarded in the word $A(p_3)$.
  \item Prepend the word $A(p_1)$ to the left of what remains after step~2.
\end{enumerate}
The resulting word is taken as $A'(p)$.

Now let a word $p$ be such that $A(p)=\omega^{n+k}$. Put $p_1=\varnothing$, let $p_2=k$ stand for the number $k$, and $p_n=\bar p_1 \bar p_2 p_n$. Then $A'(\widetilde{p_n})=\widetilde{\omega}^{n}$ and
\[
K_{A'}(\widetilde{\omega}^{n})\le 2(l(k)+1)+6+K_{A}(\omega^{n+k}),
\]
i.e.
\[
K(\widetilde{\omega})\le K_{A'}(\widetilde{\omega})\le\lim_{n\to\infty}\Bigl(\frac{C}{n}+\frac{K_{A}(\omega^{n+k})}{n+k}\cdot\frac{n+k}{n}\Bigr)\le K_{A}(\omega)=K(\omega).
\]
The reverse inequality is obtained analogously, taking $\widetilde{p_n}=\bar p_1 \bar p_2 p_n$ with $A(p_1)=\omega^{k}$, $p_2=0$ and $A(p_n)=\widetilde{\omega}^{n-k}$.
\end{proof}

\begin{lemma}[Corollary of 1.3]
The sets $\bar A_{t}=\{\omega:K(\omega)=t\}$, $\check A_{t}=\{\omega:K(\omega)<t\}$, $\hat A_{t}=\{\omega:K(\omega)>t\}$ are invariant under the shift transformation $\sigma$.
\end{lemma}

\begin{lemma}
The sets $\bar A_{t}$, $\check A_{t}$, $\hat A_{t}$ are measurable.
\end{lemma}

\begin{proof}
We show measurability of the set $\check A_{t}$ (the others are handled analogously). Indeed,
\[
\check A_{t}=\{\omega:K(\omega)<t\}=\bigcup_{k=1}^{\infty}\bigcup_{N=1}^{\infty}\bigcap_{n>N}\{\omega:K(\omega^{n})<(t-1/k)n\}.
\]
But for fixed $k$ and $n$ the set in braces is a union of a finite number of cylinders, and hence is measurable; therefore so is the set $\check A_{t}$.
\end{proof}

\begin{lemma}
If $\mu\in EM(\Omega,\sigma)$, then $K(\omega)\ge h_{\mu}(\sigma)$ for $\mu$-almost all $\omega\in\Omega$.
\end{lemma}

\begin{proof}
Suppose the contrary. Put
\[
Q=\{\omega:K(\omega)<h_{\mu}(\sigma)\},\quad \mu Q\ne 0.
\]
By Lemmas 1.3 and 1.4 the set $Q$ is invariant and measurable; consequently $\mu Q=1$ (by ergodicity of $\mu$). We have the decomposition $Q=\bigcup_{r\in\Zp}Q_{r}$, where
\[
Q_{r}=\{\omega:K(\omega)<h_{\mu}(\sigma)-1/r\}.
\]
Since the sets $Q_{r}$ are also invariant and measurable, and moreover
\[
Q_{1}\subseteq Q_{2}\subseteq\ldots\quad\text{and}\quad\bigcup_{r\in\Zp}Q_{r}=Q,
\]
there exists $R$ such that $\mu Q_{R}=1$. In turn,
\[
Q_{R}=\bigcup_{k=1}^{\infty}Q_{R,k},
\]
where $Q_{R,k}=\{\omega:K(\omega^{l})<(h_{\mu}(\sigma)-1/R)\,l\ \text{for all}\ l>k\}$. Analogously there exists $K$ such that for $k\ge K$, $\mu Q_{R,k}>1-\delta$ ($\delta>0$ arbitrary).

Further, let $\varepsilon<\min(1/R,1-\delta)$, and let $N=N(\varepsilon)$ and the sets $A_{n}$ and $B_{n}$ satisfy the condition of the well-known consequence of the Shannon--McMillan--Breiman theorem (see e.g.\ \cite{2}). In other words, for all $n>N$ we have $\Omega=A_{n}\cup B_{n}$, with $\mu(A_{n})<\varepsilon$, and for any $\omega\in B_{n}$
\[
2^{-n(h_{\mu}(\sigma)+\varepsilon)}\le\mu(C(\omega^{n}))\le 2^{-n(h_{\mu}(\sigma)-\varepsilon)}.
\]

Put
\[
Q_{R,k}^{A}=Q_{R,k}\cap A_{k},\quad Q_{R,k}^{B}=Q_{R,k}\cap B_{k}.
\]
Since $Q_{R,k}^{A}\subseteq A_{k}$, for all $k>\max(N(\varepsilon),K)$,
\[
\mu Q_{R,k}^{A}\le\mu A_{k}<\varepsilon\quad\text{and}\quad\mu Q_{R,k}^{B}>1-\delta-\varepsilon>0.\tag{$\ast$}
\]
On the other hand, if $\omega\in Q_{R,k}^{B}$, then $K(\omega^{k})\le k(h_{\mu}(\sigma)-1/R)$. Hence,
\[
\card\{\omega^{k}:\omega\in Q_{R,k}^{B}\}\le 2^{k(h_{\mu}(\sigma)-1/R)+1},
\]
and
\[
\mu(Q_{R,k}^{B})\le 2^{k(h_{\mu}(\sigma)-1/R)+1}\cdot 2^{-k(h_{\mu}(\sigma)-\varepsilon)}\le 2^{k(\varepsilon-1/R)+1}.
\]
Therefore $\lim_{k\to\infty}\mu(Q_{R,k}^{B})=0$, contradicting ($\ast$). The proof is complete.
\end{proof}

\begin{lemma}
Let $\beta=\{B_{1},\ldots,B_{M}\}$ be a finite measurable partition; $r,k\in\Zp$. Put
\[
p_{m}^{r,k}(\omega,n)=\frac{\sum_{i=0}^{[(n-r)/k]} \chi_{B_{m}}(\sigma^{ik+r}\omega)}{[n/k]},
\]
where $\chi_{B_{m}}$ is the characteristic function of the set $B_{m}$.
Then for any $k\in\Zp$ and any measure $\mu\in EM(\Omega,\sigma)$ the following two statements are simultaneously true for $\mu$-almost all $\omega\in\Omega$:
\begin{enumerate}[label=\textup{(\alph*)}]
  \item For all $1\le m\le M$ there exists
  \[
  p_{m}^{r,k}(\omega)=\lim_{n\to\infty} p_{m}^{r,k}(\omega,n).
  \]
  \item There exists $r<k$ such that
  \[
  -\sum_{m=1}^{M} p_{m}^{r,k}(\omega)\log p_{m}^{r,k}(\omega)\le H_{\mu}(\beta).
  \]
\end{enumerate}
\end{lemma}

\begin{proof}
Indeed, since $\mu\in EM(\Omega,\sigma)$, we have $\mu\in M(\Omega,\sigma^{k})$, and the validity of (a) follows directly from the Birkhoff--Khinchin ergodic theorem. From the same theorem it follows that for $\mu$-almost all $\omega\in\Omega$,
\[
p_{m}^{0,1}(\omega)=\mu(B_{m})\quad\text{for all}\ 1\le m\le M.
\]
But then the validity of (b) for the same $\omega$ follows from the concavity of entropy and the equality
\[
-\frac{1}{k}\sum_{r=0}^{k-1} p_{m}^{r,k}(\omega)=p_{m}^{0,1}(\omega).
\]
\end{proof}

\begin{lemma}[obvious]
If $t_{n}=kn+r$ is an arithmetic progression, then
\[
K(\omega)=\limsup_{n\to\infty}\frac{K(\omega^{t_{n}})}{t_{n}}.
\]
\end{lemma}

\begin{lemma}
If $\mu\in EM(\Omega,\sigma)$, then
\[
K(\omega)\le h_{\mu}(\sigma)
\]
for $\mu$-almost all $\omega\in\Omega$.
\end{lemma}

\begin{proof}
The proof uses a simple modification of a construction used by Kolmogorov (see \cite[Theorem 5.3]{7}). We shall assume that all words $\omega^{k}$ ($\omega\in\Omega$, $k$ arbitrary) are ordered, e.g.\ lexicographically. Now fix some $k$ and represent an arbitrary word $\omega^{n}$ ($n=ik+r$, $r<k$) in the form
\[
\omega^{n}=\omega_{0}^{r}\omega_{1}^{k}\omega_{2}^{k}\ldots\omega_{i}^{k}.
\]
Denote by $s_{j}=s_{j}(\omega^{n})$ the number of times the $j$-th word of the set $\Omega^{k}$ occurs among the words $\omega_{s}^{k}$ ($1\le s\le i$). The set of numbers $\{s_{j}=s_{j}(\omega^{n})\}_{j=1}^{M}$, where $M=\card\{\Omega^{k}\}$, is called the \emph{frequency set} of the word $\omega^{n}$. Moreover, we denote by $h(\omega^{n})$ the logarithm of the number of all words of length $n$ having the same frequency set as $\omega^{n}$, i.e.
\[
h(\omega^{n})=\log\frac{i!}{s_{1}!\ldots s_{M}!},
\]
and by $N(\omega^{n})$ the index of $\omega^{n}$ among these words.

Finally, it is clear that there exist $R\in\Zp$ and a computable function $A_{0}=A_{0}(p)$ such that $K_{A_{0}}(\omega^{t})<R$ for any $\omega$ if $t<k$. Then the word $\omega^{n}$ is uniquely recovered from the set of numbers
\[
\{k,i,s_{1},\ldots,s_{M},r,A_{0}^{-1}(\omega_{0}^{r}),N(\omega^{n})\},
\]
or what is the same, from the binary word
\[
p=\bar k\,\bar i\,\bar s_{1}\ldots \bar s_{M}\,\bar r\,\overline{A_{0}^{-1}(\omega_{0}^{r})}\,\log N(\omega^{n}).
\]

We shall call the computable function $A^{\ast}$ effecting this encoding of the word $\omega^{n}$ into the word $p$ the \emph{frequency-encoding function}. Thus,
\[
K_{A^{\ast}}(\omega^{n})\le 2\bigl(l(k)+l(i)+\sum_{m=1}^{M} l(s_{m})+l(r)+R\bigr)+h(\omega^{n}),
\]
or, since
\[
i=\Bigl[\frac{n}{k}\Bigr]\quad\text{and}\quad l(s_{m})\le l(i)\le[\log i]+1
\]
for all $m$, we have
\[
K_{A^{\ast}}(\omega^{n})\le h(\omega^{n})+o(n).
\]

Applying Stirling's formula
\[
n!=\sqrt{2\pi n}\,\Bigl(\frac{n}{e}\Bigr)^{n}(1+o(1)),
\]
we get
\[
h(\omega^{n})\le -i\sum_{m=1}^{M}\frac{s_{m}(\omega^{n})}{i}\log\Bigl(\frac{s_{m}(\omega^{n})}{i}\Bigr);
\]
in the notation of Lemma~1.7,
\[
h(\omega^{n})\le -i\sum_{m=1}^{M} p_{m}^{r,k}(\omega,n)\log p_{m}^{r,k}(\omega,n).
\]

But then, by Lemmas 1.7 and 1.8, for $\mu$-almost all $\omega$,
\[
K(\omega)\le K_{A^{\ast}}(\omega)\le\frac{H_{\mu}(\beta_{k})}{k},\tag{1}
\]
where $\beta_{k}=\{B_{1},\ldots,B_{M}\}$ is the partition into all cylinders of length $k$, i.e.\ $\beta_{k}=\{C(\omega^{k})\}_{\omega\in\Omega}$. The validity of Lemma~1.9 now easily follows from the arbitrariness of $k$ in inequality (1) and Lemma 1.2. The proof is complete.
\end{proof}

Theorem~1.1 obviously follows from Lemmas 1.6 and 1.9.

The statement of Theorem~1.1, besides its independent interest, in combination with known facts of the entropy theory of DS, allows us to answer a number of questions that remain open in the purely topological treatment of symbolic DS.

\begin{proposition}
We have earlier shown (see Theorem~5.4 of \cite{1}) that for any $\omega\in\Omega$,
\[
K(\omega)\le H(\omega)\le h(\sigma\mid\Omega),
\]
where $H(\omega)$ is the combinatorial entropy of $\omega$. If now $\mu_{M}$ is the measure of maximal entropy (such a measure always exists for a symbolic DS), then for $\mu_{M}$-almost all $\omega\in\Omega$,
\[
K(\omega)=H(\omega)=h(\sigma\mid\Omega).
\]
\end{proposition}

\begin{proposition}
There exist minimal DS for which
\[
K(\omega)\not\equiv\textup{const}.
\]
\end{proposition}

The validity of this assertion follows from the existence of minimal DS (for which $H(\omega)\equiv h(\sigma\mid\Omega)$) admitting invariant measures with different entropies (see \cite{20}) and the assertion of Theorem~1.1.

Further development of these questions can be found in \S4 of this article.

It seems interesting to consider the question of a \emph{constructive description} of sequences whose complexity does not exceed the entropy. An answer to this question within the framework of restrictions adopted in information theory is given in the following assertion. Note that its proof is a ``translation'' into the complexity language of the proof of Shannon's classical result (see \cite[Theorem 4]{15}).

\begin{proposition}
If $\mu\in EM(\Omega,\sigma)$ is a computable measure (see the definition in \cite{7}) and $\omega_{0}$ ``satisfies'' the Shannon--McMillan--Breiman theorem, that is,
\[
\lim_{n\to\infty}-(1/n)\log\mu(C(\omega_{0}^{n}))=h_{\mu}(\sigma),
\]
then $K(\omega_{0})\le h_{\mu}(\sigma)$.
\end{proposition}

\begin{proof}
Let the function $A=A(p)$ be defined on words $p=\bar p_{1}p_{2}$ so that if $p_{1}=n$, $p_{2}=k$, then $A(p)=\omega^{n}$ if and only if the cylinder $C(\omega^{n})$ has index $k$ among all cylinders $C(\omega^{n})$ ordered (by decreasing magnitude) according to their measures. Note that computability of $A$ follows from computability of the measure $\mu$. Suppose $K(\omega_{0})>h'>h_{\mu}(\sigma)$. Then, since $K_{A}(\omega_{0})\ge K(\omega_{0})$, there exists a sequence $\{n_{i}\}_{i\in\Zp}$ such that for all $n_{i}$
\[
K_{A}(\omega_{0}^{n_{i}})>n_{i}h'.
\]
Since
\[
K_{A}(\omega_{0}^{n_{i}})\le 2\log n_{i}+\log(N_{\mu}(\omega_{0}^{n_{i}})),
\]
where $N_{\mu}(\omega_{0}^{n_{i}})$ is the index of the cylinder $C(\omega_{0}^{n_{i}})$ according to its measure, we have
\[
\lim_{i\to\infty}\frac{\log(N_{\mu}(\omega_{0}^{n_{i}}))}{n_{i}}>h'.
\]
Set
\[
\Phi(\omega_{0}^{n_{i}})=\{\omega^{n_{i}}:N_{\mu}(\omega^{n_{i}})<N_{\mu}(\omega_{0}^{n_{i}})\}
\]
and put
\[
S_{n_{i}}=\sum_{\omega^{n_{i}}\in\Phi(\omega_{0}^{n_{i}})}\mu(C(\omega^{n_{i}})).
\]
In view of the normalization of $\mu$,
\[
\mu(S_{n_{i}})\le 1\quad\text{for all}\ i\in\Zp.
\]
On the other hand,
\[
\lim_{i\to\infty}\frac{\log S_{n_{i}}}{n_{i}}\ge\lim_{i\to\infty}\frac{\log([2^{n_{i}h'}]\cdot\mu(C(\omega_{0}^{n_{i}})))}{n_{i}}\ge h'-h_{\mu}(\sigma)>0.
\]
The proof of Proposition~1.12 is complete.
\end{proof}

\section{Properties of the quantity $K(x,T\mid\co)$ --- the complexity of the trajectory of a point $x$ relative to a cover $\co$}

In this section, for an arbitrary DS, the notion of \emph{complexity of a trajectory relative to a cover} is introduced and studied. We note that the results of this section, besides their auxiliary character (they are essentially used in \S3 --- the main section of the present work), are also of independent interest, allowing one, in particular, to estimate the complexity of the classical Sturmian trajectories of Hedlund--Morse.

\begin{definition}
Let $\co=\{A_{1},\ldots,A_{k}\}$ be a finite cover of $X$. The quantity
\[
K(x,T\mid\co)=\limsup_{n\to\infty}(1/n)\min_{\omega\in\phi_{\co}(x)} K(\omega^{n})
\]
will be called the \emph{complexity of the trajectory of the point $x\in X$ relative to the cover $\co$}.
\end{definition}

The quantity $K(x,T\mid\co)$ possesses the following entropy-like properties:

\begin{proposition}
$K(x,T\mid\co_{1})\le K(x,T\mid\co_{2})$ if $\co_{2}\ge\co_{1}$.
\end{proposition}

\begin{proposition}
$K(x,T\mid\co_{1}\vee\co_{2})\le K(x,T\mid\co_{1})+K(x,T\mid\co_{2})$.
\end{proposition}

\begin{proposition}
$K(x,T\mid\co^{k})=K(x,T\mid\co)$ for any $k\in\Zp$.
\end{proposition}

We prove Property 2.2 (the proofs of the other properties are analogous).

Let $\co_{1}=\{A_{1},\ldots,A_{k}\}$, $\co_{2}=\{A'_{1},\ldots,A'_{l}\}$ and $\co_{1}\le\co_{2}$.

Clearly there exists a computable function $A_{0}\colon\{1,\ldots,l\}\to\{1,\ldots,k\}$ such that if $A_{0}(j)=i$, then $A'_{j}\subseteq A_{i}$. If now $A$ is an arbitrary a.\,opt.\,f., then $\widetilde A=A_{0}\circ A$ is computable and, moreover, if $A(p)\in\{(\phi_{\co_{2}}(x))^{n}\}$, then $\widetilde A(p)\in\{(\phi_{\co_{1}}(x))^{n}\}$. From this, by the arbitrariness of $n$, we obtain Property 2.2.

The following simple but extremely useful statement holds.

\begin{proposition}
$K(x,T\mid\co)\le\inf_{\omega\in\phi_{\co}(x)} K(\omega)$; in particular, if $\co$ is a partition, then $K(x,T\mid\co)=K(\phi_{\co}(x))$.
\end{proposition}

Analogously to the fact that for almost all sequences of a symbolic DS the complexity coincided with the entropy, for the complexity of a trajectory relative to a partition we have:

\begin{lemma}
Let $\beta$ be a finite measurable partition and $\mu\in EM(X,T)$. Then for $\mu$-almost all $x\in X$,
\[
K(x,T\mid\beta)=h_{\mu}(T,\beta).
\]
\end{lemma}

\begin{proof}
As already noted in \S0, if $\mu\in EM(X,T)$, then $\widetilde\mu_{\beta}\in EM(\Omega_{\beta},\sigma)$; it is well known that in that case $h_{\mu}(T,\beta)=h_{\widetilde{\mu_{\beta}}}(\sigma\mid\Omega_{\beta})$. But by Theorem~1.1
\[
\widetilde{\mu}(\{\omega\in\Omega_{\beta}:K(\omega)=h_{\mu}(T,\beta)\})=1.
\]
Put $Q=\phi_{\beta}^{-1}(\Omega_{\beta})$. For $x\in Q$,
\[
K(x,T\mid\beta)=K(\phi_{\beta}(x))=h_{\mu}(T,\beta).
\]
Hence $\mu Q=\widetilde\mu_{\beta}\Omega_{\beta}=1$.
\end{proof}

\begin{corollary}
If $\mu\in EM(X,T)$ and $\beta$ is a generator for the measure $\mu$, then for $\mu$-almost all $x\in X$,
\[
K(x,T\mid\beta)=h_{\mu}(T);
\]
and for any partition $\beta$ the set
\[
Q=\{x:K(x,T\mid\beta)>\sup_{\mu\in M(X,T)} h_{\mu}(T)\}
\]
has invariant measure zero.
\end{corollary}

Throughout the remainder of \S2 the quantity $\sup_{x\in X} K(x,T\mid\co)$ is investigated.

The first of the statements relating to this circle of questions looks somewhat unexpected.

\begin{proposition}
For any non-periodic point $x_{0}\in X$ and any number $N\in\Zp$ there exists a finite measurable partition $\beta$ such that
\[
K(x_{0},T\mid\beta)=\log N.
\]
\end{proposition}

\begin{proof}
Let $\omega_{0}\in\Lambda_{N=\{0,1,\ldots,N-1\}}$ and $K(\omega_{0})=\log N$ (such sequences form a set of full measure by Theorem~1.1). For each $i$ ($0\le i\le N-1$) form the set
\[
B_{i}=\{x\in X:\ \text{there exists}\ k\in\Zp\ \text{such that}\ T^{k}x_{0}=x\ \text{and}\ \omega_{0}(k)=i\}
\]
and put
\[
B_{N}=X\setminus\bigcup_{i=0}^{N-1}B_{i}.
\]
It is easy to see that the partition $\beta=\{B_{1},\ldots,B_{N}\}$ is measurable and $\phi_{\beta}(x_{0})=\omega_{0}$, i.e.\ $K(x_{0},T\mid\beta)=\log N$.
\end{proof}

Note that it is precisely Proposition~2.8 that prevents one from introducing the concept $K(x,T)$ --- the simple (without a cover) complexity of a trajectory --- in the traditional entropy-theoretic manner, by putting
\[
K(x,T)=\sup K(x,T\mid\beta),
\]
where $\sup$ is taken over all finite measurable partitions of $X$.

Another, also entropy-theoretic, approach to introducing the quantity $K(x,T)$ for metric DS is presented in \cite{5} (there this quantity is denoted by $K^{0}(x,T)$).

In what follows we shall assume that $(X,T)$ is a topological dynamical system.

\begin{proposition}
If $u=\{U_{1},\ldots,U_{l}\}$ is a finite open cover, then for all $x\in X$,
\[
K(x,T\mid u)\le h(T,u).
\]
\end{proposition}

\begin{proof}
Indeed, let $h'>h(T,u)$; then there exist $N\in\Zp$ and a cover $\widetilde u$ (a subcover of the cover $u^{N}$) such that $\log\card\{\widetilde u\}<h'\cdot N$. Since $\widetilde u$ is a cover, there exists $\omega\in\phi_{u}(x)$ such that for all $k\in\Zp$,
\[
U_{\omega(kN)}\cap T^{-1}U_{\omega(kN+1)}\cap\ldots\cap T^{-N+1}U_{\omega(kN+N-1)}\in\widetilde u.
\]
Hence, by Lemma~1.8, Proposition~2.5 and the properties of complexity, we obtain
\[
K(x,T\mid u)\le\frac{1}{N}\limsup_{k\to\infty}\frac{K(\omega^{N\cdot k})}{k}\le\frac{\log\card\widetilde u}{N}<h'.
\]
\end{proof}

Returning to the case of a partition, we present two estimates for the quantity $\sup_{x\in X} K(x,T\mid\co)$, based respectively on a topological and a metric estimate of the massivity of the set
\[
W(\co)=\{x\in\bar A_{i}\cap\bar A_{j};\ i\ne j\}
\]
--- the boundary of the cover $\co$.

\begin{proposition}
Let $S_{\co}$ be the dynamical analogue of the index of a cover considered in \cite{4} (there it is denoted simply $S$). The estimate
\[
S_{\co}\ge\sup_{x\in X} K(x,T\mid\co)-h(T)
\]
holds.
\end{proposition}

\begin{proposition}
If the set $W(\co)$ has invariant measure zero, then $K(x,T\mid\co)\le h(T)$.
\end{proposition}

\begin{proof}
In \cite{22} it is shown that under the hypotheses of Proposition~2.11 there exists a measure $\nu\in M(X,T)$ such that $h(\sigma\mid\Omega_{\co})=h_{\nu}(T,\co)$. But then by the Dinaburg--Goodwyn theorem and the inequality $K(\omega)\le h(\sigma\mid\Omega)$, we have
\[
K(\omega)\le h(T)\quad\text{for all}\ \omega\in\Omega_{\co}.
\]

But if $\omega\in\Omega_{\co}$, then \emph{a fortiori} $\omega\in\Omega_{\co}$, i.e.
\[
K(x,T\mid\co)=K(\phi_{\co}(x))\le h(T).
\]
\end{proof}

With the help of Proposition~2.11 one can estimate the complexity of the classical Sturmian trajectories of Hedlund--Morse (see \cite{26}). Indeed, let $X=[0,1)$ be the unit circle, and $T\colon X\to X$ the rotation by an angle $\alpha$ (i.e.\ $x\mapsto x+\alpha$; $\alpha$ irrational). It is well known that such a DS is strictly ergodic; its unique invariant measure $m$ is the usual Lebesgue measure, and $h_{m}(T)=0$. Further, denote by $\beta=\{B_{1},\ldots,B_{k}\}$ the partition determined by the condition $B_{i}=[r_{i},r_{i+1})$, where
\[
0=r_{1}<r_{2}<\ldots<r_{k+1}=1.
\]
The elements of the space $\Omega_{\beta}$ are called \emph{Sturmian trajectories}. Since $m(W(\beta))=m(\{r_{0},r_{1},\ldots,r_{k+1}\})=0$, by 2.11 we obtain

\begin{corollary}
For all $x\in X$, $K(x,T\mid\beta)=K(\phi_{\beta}(x))=0$, i.e.\ the complexity of Sturmian trajectories equals zero.
\end{corollary}

\section{Complexity of trajectories of a topological dynamical system}

In this section, with each trajectory of a topological dynamical system we shall associate a number $K(x,T)$ characterizing the degree of complexity of the behavior of this trajectory in the phase space of the system. In so doing, two main statements of the present paper will be established, namely

\begin{theorem}
If $\mu\in EM(X,T)$, then
\[
K(x,T)=h_{\mu}(T)
\]
for $\mu$-almost all $x\in X$.
\end{theorem}

\begin{theorem}
For any point $x\in X$,
\[
K(x,T)\le h_{T}(x),
\]
where $h_{T}(x)$ is the entropy of the point $x$ in the sense of Kamae \cite{24}.
\end{theorem}

\subsection*{1.~Definition}

The quantity
\[
K(x,T)=\sup_{u} K(x,T\mid u),
\]
where the $\sup$ is taken over all finite open covers of the space $X$, will be called the \emph{complexity of the trajectory of the point $x$}.

\begin{remark}
Although the present definition makes sense for arbitrary topological DS, most of the results of \S3 are obtained under the assumption that $X$ is a metric compactum.
\end{remark}

All covers considered below are assumed to be open and finite.

In my view, the following statement (not used in the sequel) is curious:

\begin{proposition}[proof omitted]
Let the DS $(X,T)$ and $(Y,S)$ be topologically conjugate, with $\pi\colon X\to Y$ the conjugating homeomorphism and $\pi(x)=y$. Then
\[
K(x,T)=K(y,S).
\]
\end{proposition}

From Properties 2.2, 2.4, 2.6 and well-known properties of topological DS we obtain:

\begin{proposition}
If $\lim_{i\to\infty} d(u_{i})=0$ for a family of covers, then
\[
K(x,T)=\sup_{i\in\Zp} K(x,T\mid u_{i}).
\]
\end{proposition}

\begin{corollary}
If a cover $u$ is a \emph{topological generator} of the DS $(X,T)$, then
\[
K(x,T)=K(x,T\mid u),
\]
and in particular, for a symbolic DS,
\[
K(\omega,\sigma)=K(\omega).
\]
\end{corollary}

\begin{proposition}
For all $x\in X$,
\[
K(x,T)\le h(T).
\]
\end{proposition}

\begin{remark}
Sharpening Proposition~3.6, one can show that $K(x,T)\le h(T\mid\overline{O(x)})$, where $\overline{O(x)}$ is the closure of the trajectory of the point $x$. A substantially sharper estimate of the complexity of a concrete trajectory is given in Theorem~3.2.

We also note that consideration of the simplest examples of DS not possessing a measure of maximal entropy shows that there may not exist trajectories of maximal complexity, i.e.\ it is not excluded that $K(x,T)<h(T)$ for all $x\in X$.
\end{remark}

Our immediate goal is the proof of Theorem~3.1.

We present auxiliary results.

\begin{definition}
A set $A\in\fM$ will be called $\mu$-\emph{continuous} if $\mu(\nu A)=0$, where $\nu A$ denotes the boundary of $A$.

A cover $u=\{U_{1},\ldots,U_{k}\}$ will be called $\mu$-continuous if all the sets $U_{i}$ ($1\le i\le k$) are $\mu$-continuous.
\end{definition}

\begin{lemma}
For any cover $u$ there exists a $\mu$-continuous cover $v$ such that $v\ge u$.
\end{lemma}

\begin{proof}
Let $\delta(u)$ be the Lebesgue number of the cover $u$. For each point $x\in X$ there exists a neighborhood $O(x)$ such that $d(O(x))<\delta$ and the set $O(x)$ will be $\mu$-continuous. For the cover $0=\{O(x)\}_{x\in X}$ of the compactum $X$ by such sets, there is a finite subcover $v$, which is the required one.
\end{proof}

\begin{corollary}
From Property 2.2 and Lemma~3.8 it follows that
\[
K(x,T)=\sup K(x,T\mid u),
\]
where $\sup$ is taken only over $\mu$-continuous covers $u$ of the compactum $X$.
\end{corollary}

\begin{lemma}
For any cover $u$ and any $\varepsilon>0$ there exists a cover $v$ such that:
\begin{enumerate}[label=\arabic*.]
  \item $v\ge u$;
  \item $v$ is $\mu$-continuous;
  \item $\mu(W(v))<\varepsilon$, where, as before,
  \[
  W(v)=\{x\in\bigcup_{i\ne j}\bar V_{i}\cap\bar V_{j}\}.
  \]
\end{enumerate}
\end{lemma}

\begin{proof}
By Lemma~3.8 there exists a $\mu$-continuous cover $v'\ge u$. We now describe an iterative procedure by which we obtain the required cover $v$ from $v'$. Let $M=\card v'$ (i.e.\ $v'=\{V_{1},\ldots,V_{M}\}$) and $\varepsilon_{0}<\varepsilon/M^{2}$. At each step of the iteration we choose a pair of sets such that $\mu(V_{i}^{k}\cap V_{j}^{k})>\varepsilon_{0}$ and construct a cover $v^{k+1}=\{V_{1}^{k+1},\ldots,V_{M}^{k+1}\}$, where $V_{s}^{k+1}=V_{s}^{k}$ for $s\ne j$ and $V_{j}^{k+1}\subseteq V_{j}^{k}$, with:
\begin{enumerate}
  \item $V_{j}^{k+1}$ is $\mu$-continuous;
  \item $\mu(V_{i}^{k+1}\cap V_{j}^{k+1})<\varepsilon_{0}$.
\end{enumerate}
It is clear that the iterative process so defined ends in a finite number of steps, and the resulting cover $v$ is the required one.

We describe a step of the iteration. By the $\mu$-continuity of the sets $V_{i}^{k}$ and $V_{j}^{k}$, there exists a $\mu$-continuous open set $O_{ij}$ such that
\[
O_{ij}\supseteq\nu(V_{i}^{k}\cap V_{j}^{k})\quad\text{and}\quad\mu(O_{ij})<\varepsilon_{0}.
\]
Put
\[
V_{j}^{k+1}=(V_{j}^{k}\setminus V_{i}^{k})\cup(O_{ij}\cap V_{j}^{k}).
\]
It is easy to see that the set $V_{j}^{k+1}$ is open, $\mu$-continuous, and moreover,
\[
\mu(V_{j}^{k+1}\cap V_{i}^{k})\le\mu(O_{ij})<\varepsilon_{0}.
\]
\end{proof}

In what follows, for a cover $u=\{U_{1},\ldots,U_{M}\}$ we denote by $\beta(u)$ the partition of the compactum $X$ into sets $B_{i}$ ($1\le i\le M$) defined by
\begin{align*}
B_{1} &= U_{1};\\
B_{2} &= U_{2}\setminus U_{1};\\
&\vdots\\
B_{M} &= U_{M}\setminus\bigcup_{i=1}^{M-1} U_{i}.
\end{align*}

\begin{lemma}[obvious]
If a cover $u$ is $\mu$-continuous, then so are the covers
\[
\beta(u),\ T^{-1}(u),\ u^{N},\ \beta^{N}(u).
\]
\end{lemma}

We shall need the following standard construction from the theory of dynamical systems.

To every point $x\in X$ and number $n\in\Zp$ we associate a measure $\mu_{x,n}$ defined by
\[
\mu_{x,n}=\frac{1}{n}(\delta_{x}+\delta_{Tx}+\ldots+\delta_{T^{n-1}x}),
\]
where $\delta_{x}$ is the measure concentrated at the point $x$.

It is well known (see \cite{12,20}) that for any $x\in X$ the set $V_{T}(x)$ --- the limit set (in the weak topology) of the family of measures $\{\mu_{x,n}\}_{n\in\Zp}$ --- possesses two properties, namely:
\begin{enumerate}
  \item $V_{T}(x)\ne\varnothing$;
  \item $V_{T}(x)\subseteq M(X,T)$.
\end{enumerate}

By an \emph{ergodic decomposition} of the dynamical system $(X,T)$ one means a representation of $X$ in the following form:
\[
X=\bigcup_{\mu\in EM(X,T)} M_{\mu}\cup N,
\]
where
\begin{enumerate}
  \item $x\in M_{\mu}\iff V_{T}(x)=\{\mu\}$;
  \item $\mu(M_{\mu})=1$ for any $\mu\in EM(X,T)$;
  \item the set $N$ is of invariant measure zero.
\end{enumerate}

In the next two lemmas the relationship between the concept of $\mu$-continuity of a set and the decomposition of the space $X$ into ergodic sets is established. The first of them is well known.

\begin{lemma}
If a sequence of measures $\mu_{i}$ converges (in the weak topology) to a measure $\mu$ ($\mu_{i}\Rightarrow\mu$), then for every $\mu$-continuous set $B$,
\[
\lim_{i\to\infty}\mu_{i}(B)=\mu(B).
\]
\end{lemma}

\begin{lemma}
Let $\mu\in EM(X,T)$, $\bar\mu$ its upper measure, $B$ a $\mu$-continuous set with $\mu(B)<\tau$. Then for every $\varepsilon>0$ there exists an integer $L$ such that the set
\[
P_{L}=\{x:\mu_{x,l}(B)<\tau\ \text{for}\ l>L\}
\]
satisfies $\mu P_{L}>1-\varepsilon$.
\end{lemma}

\begin{proof}
Indeed, for all $x\in M_{\mu}$, by Lemma~3.12, $\lim_{l\to\infty}\mu_{x,l}(B)=\mu(B)$. Thus for each $x\in M_{\mu}$ there exists $L(x)$ such that
\[
\mu_{x,l}(B)<\tau\quad\text{for}\ l>L(x).
\]
Denote $P_{k}=\{x:x\in M_{\mu}\ \text{and}\ L(x)<k\}$; then
\[
P_{1}\subseteq P_{2}\subseteq\ldots\quad\text{and}\quad\bigcup_{k=1}^{\infty}P_{k}=M_{\mu}.
\]
Now the existence of a number $L$ with the required properties follows from a well-known measure-theoretic theorem.
\end{proof}

The proof and role of Lemma~3.14 are analogous to the proof and place of Lemmas~1.4 and~1.5 in \S1.

\begin{lemma}
The sets $X_{t,u}=\{x:K(x,T\mid u)<t\}$ are invariant and measurable for all $t\in\Rp$.
\end{lemma}

\begin{lemma}
Let $\mu\in EM(X,T)$. For $\mu$-almost all $x\in X$,
\[
K(x,T)\ge h_{\mu}(T).
\]
\end{lemma}

\begin{proof}
Indeed, suppose there exists $h'<h_{\mu}(T)$ such that $\mu(X_{h'}=\{x:K(x,T)<h'\})\ne 0$. Consequently, for any cover $u$ and any $\varepsilon>0$, by arguments analogous to the proof of Lemma~1.10, we obtain the existence of a number $k_{0}\in\Zp$ such that $\mu(Z_{k_{0},h'})>1-\varepsilon$, where
\[
Z_{k_{0},h'}=\{x:\min_{\omega^{k}\in\{(\psi_{u}(x))^{k}\}} K(\omega^{k})<k\cdot h'\ \text{for}\ k>k_{0}\}.
\]
For each $k\in\Zp$ define a mapping $\psi_{u,k}\colon X\to\Omega_{u}^{k}$ as follows:
\[
\omega_{0}^{k}\in\psi_{u,k}(x)\iff\omega_{0}^{k}\in\Omega_{u}^{k}\ \text{and}\ K(\omega_{0}^{k})=\min_{\omega\in\{\psi_{u}(x)\}} K(\omega^{k}).
\]
Note that for each fixed $k>k_{0}$,
\begin{equation}
\card\{\psi_{u,k}(Z_{k,h'})\}<2^{kh'+1}.\tag{1}
\end{equation}

Without loss of generality, we may assume that:
\begin{enumerate}
  \item the cover $u$ is $\mu$-continuous;
  \item $\mu(W(u))<\tau$ ($\tau>0$, arbitrary);
  \item $h_{\mu}(T,\beta(u))>h'+\varepsilon$ ($h'+\varepsilon<h_{\mu}(T)$).
\end{enumerate}
Then by Lemma~3.13 there exists $L$ such that $\mu P_{L}>1-\varepsilon$. Finally, by virtue of the consequence of the Shannon--McMillan--Breiman theorem, $\Omega_{\beta(u)}=A_{n}\cup B_{n}$ and for $n>N(\varepsilon)$:
\begin{enumerate}
  \item $\mu(B_{n})>1-\varepsilon$,
  \item $\mu(C(\omega^{n}))\ge 2^{-n(h_{\mu}(T,\beta(u))+\varepsilon)}$ for $\omega\in B_{n}$.
\end{enumerate}
Of course,
\[
\card\{\omega:\omega\in B_{n}\}\le 2^{n(h_{\mu}(T,\beta(u))+\varepsilon)}.
\]
Put $S_{n}=Z_{n,h'}\cap P_{n}\cap\phi_{\beta(u)}^{-1}(B_{n})$.

For $n>R=\max(k_{0},L,N(\varepsilon))$ we have $\mu(S_{n})>1-3\varepsilon$. Since $S_{n}\subseteq Z_{n,h'}$, for $n>R$,
\begin{equation}
\card\{\Phi_{u,n}=\{\psi_{u,n}(x):x\in S_{n}\}\}<2^{nh'+1}.\tag{2}
\end{equation}
On the other hand, if $x\in S_{n}$, then $x\in\phi_{\beta(u)}^{-1}(B_{n})$ and for $n>R$
\begin{equation}
\card\{(\phi_{\beta(u)}(x))^{n}:x\in S_{n}\}\ge(1-3\varepsilon)\cdot 2^{n(h_{\mu}(T,\beta(u))-\varepsilon)}.\tag{3}
\end{equation}
Put $\Theta_{u}(x,n)=\card\{(\phi_{u}(x))^{n}\}$; then from (3) we obtain:
\[
\sum_{x\in S_{n}}\Theta_{\beta(u)}(x,n)\ge(1-3\varepsilon)\cdot 2^{n(h_{\mu}(T,\beta(u))-\varepsilon)}.
\]
On the other hand, from (2)
\[
\sum_{x\in S_{n}}\Theta_{\beta(u)}(x,n)=\sum_{\omega^{n}\in\Phi_{u,n}}\sum_{\substack{x\in\psi_{u,n}^{-1}(\omega^{n})\\x\in S_{n}}}\Theta_{\beta(u)}(x,n)\le 2^{nh'+1}\cdot\max_{\omega^{n}\in\Phi_{u,n}}\sum_{\substack{x\in\psi_{u,n}^{-1}(\omega^{n})\\x\in S_{n}}}\Theta_{\beta(u)}(x,n).
\]

Thus, for each $n>R$ there exists $\omega^{n}\in\Phi_{u,n}$ such that
\[
G(\omega^{n})=\sum_{\substack{x\in\psi_{u,n}^{-1}(\omega^{n})\\x\in S_{n}}}\Theta_{\beta(u)}(x,n)\ge(1-3\varepsilon)\cdot 2^{n(h_{\mu}(T,\beta(u))-\varepsilon-h')-1}.
\]
Consequently,
\begin{equation}
\lim_{n\to\infty}\frac{\log(\max G(\omega^{n}))}{n}\ge h_{\mu}(T,\beta(u))-\varepsilon-h'>0.\tag{4}
\end{equation}

However, if $n>R$, $x\in S_{n}$, and moreover $\omega^{n}\in\{\psi_{u,n}(x)\}$, $\widetilde\omega^{n}=\{(\phi_{\beta(u)}(x))^{n}\}$, then the words
\[
\omega^{n}=\omega(0)\ldots\omega(n-1)\quad\text{and}\quad\widetilde\omega_{n}=\widetilde\omega(0)\ldots\widetilde\omega(n-1)
\]
may differ in not more than $n\tau$ places, since $x\in P_{n}$.

Consequently, for any $\omega^{n}\in\Phi_{u,n}$,
\[
G(\omega^{n})=\sum_{\substack{x\in\psi_{u,n}^{-1}(\omega^{n})\\x\in S_{n}}}\Theta_{\beta(u)}(x,n)\le\binom{n}{n\tau}\cdot M^{n\tau};
\]
in this formula $M=\card u$. Applying Stirling's formula, we obtain for sufficiently large $n$
\begin{equation}
\frac{\log G(\omega^{n})}{n}\le\tau\Bigl(\log\frac{1-\tau}{\tau}+\log M\Bigr)+o(1)\tag{5}
\end{equation}
also for any $\widetilde\omega_{n}\in\Phi_{u,n}$.

But since
\[
\lim_{\tau\to 0}\tau\Bigl(\log\frac{1-\tau}{\tau}+\log M\Bigr)=0,
\]
(5) contradicts (4). The proof of Lemma~3.15 is complete.
\end{proof}

\begin{lemma}
Let $\mu\in EM(X,T)$. Then $K(x,T)\le h_{\mu}(T)$ for $\mu$-almost all $x\in X$.
\end{lemma}

\begin{proof}
Let $\{u_{i}\}_{i\in\Zp}$ be a countable family of covers with $\lim_{i\to\infty} d(u_{i})=0$. Then for all $x\in X$, by Properties 3.4 and 2.5,
\[
K(x,T)=\sup_{i\in\Zp} K(x,T\mid u_{i})\le\sup_{i\in\Zp} K(x,T\mid\beta(u_{i}))
\]
and hence, for $\mu$-almost all $x\in X$, by Lemma~2.6,
\[
K(x,T)\le\sup_{i\in\Zp} h_{\mu}(T,\beta(u_{i}))\le h_{\mu}(T).
\]
\end{proof}

Theorem~3.1 follows directly from Lemmas 3.15 and 3.16.

Of independent interest is

\begin{proposition}
The partition of the space $X$ into level sets of the function $K(x,T)$ is measurable and invariant.
\end{proposition}

\begin{proof}
For a family of covers $\{u_{i}\}_{i\in\Zp}$ ($\lim_{i\to\infty} d(u_{i})=0$), denote
\begin{align*}
\bar R_{k,i}^{t} &= \{x:K(x,T\mid u_{i})\ge t-1/k\},\\
\underline R_{k,i}^{t} &= \{x:K(x,T\mid u_{i})\le t+1/k\}.
\end{align*}
By Lemma~3.14 the sets $\bar R_{k,i}^{t}$ and $\underline R_{k,i}^{t}$ are invariant and measurable. Consequently, so are the sets
\[
\bar R^{t}=\bigcap_{k=1}^{\infty}\bigcup_{i=1}^{\infty}\bar R_{k,i}^{t}\quad\text{and}\quad\underline R^{t}=\bigcap_{k=1}^{\infty}\bigcap_{i=1}^{\infty}\underline R_{k,i}^{t},
\]
and so is $\bar X_{t}=\{x:K(x,T)=t\}=\bar R^{t}\cap\underline R^{t}$.
\end{proof}

\begin{remark}
Later, in Proposition~3.20, the relationship of the decomposition of the space $X$ into the sets $\bar X_{t}$ with the ergodic decomposition of the DS $(X,T)$ is established.
\end{remark}

\subsection*{2.~Estimating the complexity of a concrete trajectory}

\begin{definition}[T.~Kamae \cite{24}]
The number
\[
h_{T}(x)=\sup_{\mu\in V_{T}(x)} h_{\mu}(T)
\]
will be called the \emph{entropy of the point $x$}; if $h_{T}(x)=0$, the point $x$ is called \emph{deterministic}.
\end{definition}

\setcounter{theorem}{1}
\begin{theorem}
For any point $x\in X$,
\[
K(x,T)\le h_{T}(x).
\]
\end{theorem}
\setcounter{theorem}{18}

\begin{proof}
Suppose the contrary: let $x_{0}\in X$ and $h'$ be such that
\[
K(x_{0},T)>h'>h_{T}(x_{0}).
\]
Then it is not hard to show that there exist: a cover $u$, a sequence $\{n_{k}\}$ ($\lim_{k\to\infty} n_{k}=\infty$), and a measure $\mu_{0}\in V_{T}(x_{0})$ such that simultaneously
\begin{enumerate}
  \item $\limsup_{n_{k}\to\infty}(1/n_{k})\min_{\omega^{n_{k}}\in\{(\psi_{u}(x_{0}))^{n_{k}}\}} K(\omega^{n_{k}})>h'$;
  \item $\mu_{x_{0},n_{k}}\Rightarrow\mu_{0}$;
  \item the cover $u$ is $\mu_{0}$-continuous;
  \item the sequence $\{n_{k}\}$ has the special form $n_{k}=t_{k}\cdot k_{0}$, where $t_{k}\in\Zp$, and $k_{0}$ is such that $H_{\mu_{0}}(\beta^{k_{0}}(u))<k_{0}\cdot h'$.
\end{enumerate}
From 1) it follows that
\begin{equation}
\lim_{n_{k}\to\infty}\frac{K((\phi_{\beta(u)}(x_{0}))^{n_{k}})}{n_{k}}>h',\tag{1}
\end{equation}
where $\beta(u)$, as before, denotes the partition obtained from the cover $u$.

On the other hand, putting
\[
p_{B}^{r,k}(x_{0},n)=\frac{\sum_{i=0}^{[(n-r)/k]} \chi_{B}(T^{ik+r}x_{0})}{[n/k]},
\]
from 2) and 3), by Lemma~3.12, for any $B\in\beta^{k_{0}}(u)$,
\begin{equation}
\lim_{n_{k}\to\infty} p_{B}^{0,1}(x_{0},n_{k})=\mu_{0}(B).\tag{2}
\end{equation}
And since for all $n_{k}$ of our form
\begin{equation}
\frac{1}{k_{0}}\sum_{r=0}^{k_{0}-1} p_{B}^{r,k_{0}}(x_{0},n_{k})=p_{B}^{0,1}(x_{0},n_{k}),\tag{3}
\end{equation}
by the continuity and concavity of entropy and relations (2) and (3), we conclude that for any sufficiently large $n_{k}$ there exists $r=r(n_{k})$ such that
\begin{align*}
-\sum_{B\in\beta^{k_{0}}(u)} p_{B}^{r,k_{0}}(x_{0},n_{k})\log p_{B}^{r,k_{0}}(x_{0},n_{k}) &\le\Bigl(h'\cdot\frac{n_{k}}{k_{0}}\Bigr) k_{0}+o(n_{k})\\
&\le h'\cdot n_{k}+o(n_{k}).
\end{align*}
But then, for the same $n_{k}$, for the frequency-encoding function $A^{\ast}$ constructed in the proof of Theorem~3.1, we obtain:
\[
\limsup_{n_{k}\to\infty}\frac{K_{A^{\ast}}((\phi_{\beta(u)}(x_{0}))^{n_{k}})}{n_{k}}\le h',
\]
which contradicts (1).
\end{proof}

\begin{corollary}
\begin{enumerate}[label=\textup{(\alph*)}]
  \item If $x\in M_{\mu}$, then $K(x,T)\le h_{\mu}(T)$.
  \item If $x$ is deterministic, then $K(x,T)=0$.
\end{enumerate}
\end{corollary}

\begin{remarks}
\begin{enumerate}
  \item The inequality in Theorem~3.2 can be strict (see \S4, Example~4.3.2).
  \item The estimate of $K(x,T)$ given by Theorem~3.2 is sharper than the estimate of Proposition~3.6, since by the Dinaburg--Goodwyn theorem $h_{T}(x)\le h(T\mid\overline{O(x)})$; the latter inequality can also be strict (see \S4, Example~4.2.2).
\end{enumerate}
\end{remarks}

In conclusion of this section we note that Theorems 3.1 and 3.2 indicate the existence of a close connection between the decomposition of the space into level sets of the function $K(x,T)$ and the classical decomposition of a DS into ergodic sets.

\begin{proposition}
Let
\[
\overline W_{t}=\Bigl\{\bigcup_{\mu\in EM(X,T)} M_{\mu}:h_{\mu}(T)\le t\Bigr\},\quad \overline X_{t}=\{x:K(x,T)\le t\};
\]
then $\overline X_{t}\supseteq \overline W_{t}$, and the set $\overline X_{t}\setminus \overline W_{t}$ is of invariant measure zero (but possibly non-empty --- see Example~4.3.2).
\end{proposition}

\section{On various approaches to the notion of a typical (complex, random) trajectory}

It seems beyond doubt that at the present time many researchers working in the most diverse parts of the theory of dynamical systems have run into ``complexity'' questions. However, the naturally arising diversity of complexity-related characteristics in the absence of a universal measure of complexity makes the exchange of ideas and results between various aspects of the theory of dynamical systems difficult.

In the present section the author has set himself the goal of bringing together and giving, as far as possible, a uniform analysis of some ``complexity'' characteristics of the theory of dynamical systems. As before, we shall not draw distinctions between the notions of point, trajectory, and sequence where this does not lead to misunderstanding.

The first question on the typicality of a trajectory was considered by A.~Poincar\'e. The set of wandering points which he singled out turned out to be a set of the first category and of invariant measure zero. After the appearance of works by Birkhoff, Krylov and Bogolyubov, an approach took shape according to which the investigation of certain typicality properties of a trajectory for a DS of general type reduces to the analysis of analogous characteristics for minimal (topological typicality) or uniquely ergodic (typicality in the measure-theoretic sense) dynamical systems. A dynamical system possessing both these properties is called \emph{strictly ergodic}.\footnote{In terminology we follow \cite{20}; in \cite{12} it is somewhat different.}

\subsection*{4.1.~Minimality, unique ergodicity and topological entropy}

\subsubsection*{4.1.1}

All trajectories of a minimal system are recurrent in the sense of Birkhoff (almost periodic). A minimal system need not be uniquely ergodic. Furstenberg \cite{21} constructed an example of a minimal system with $h(T)>0$.

\subsubsection*{4.1.2}

Within the combinatorial approach to problems of ergodic theory, many authors (see \cite{17} and references in \cite{8}) have given constructive examples of minimal or strictly ergodic systems. The final result, due to Grillenberger \cite{23}, is the following: for any number $h<\log N$ there exists a constructively describable sequence $\omega\in\Lambda_{N}$ such that the DS $(\overline O(\omega),\sigma)$ is strictly ergodic and $h(\sigma\mid\overline O(\omega))=h$.

\subsection*{4.2.~Regularity, entropy of a point in the sense of Kamae, combinatorial entropy of a trajectory}

\subsubsection*{4.2.1}

In the case of a DS of general type, the analogue of the notion of unique ergodicity is the notion of $\mu$-\emph{regularity}. By definition, a point $x$ is called $\mu$-regular if $V_{T}(x)=\{\mu\}$. Of course, $h_{T}(x)=h_{\mu}(T)$ for every $\mu$-regular point $x$. For an ergodic measure, Bowen \cite{19} showed\footnote{Here the quantity $h(T\mid M_{\mu})$ is understood in the sense of \cite{19}.} that $h(T\mid M_{\mu})=h_{\mu}(T)$.

\subsubsection*{4.2.2}

By the Dinaburg--Goodwyn theorem,
\[
h_{T}(x)\le h(T\mid\overline O(x));
\]
thus the Kamae entropy does not exceed the combinatorial entropy. The example of the sequence
\[
\omega_{0}=p_{0}\,0\,p_{1}\,0\,0\,p_{2}\,0\,0\,0\,\ldots\,p_{k}\underbrace{0\ldots 0}_{2^{k}},
\]
where $p_{k}$ is the $k$-th binary word, provides an example of a point of the symbolic DS $(\Lambda_{2},\sigma)$ for which this inequality is strict. Indeed, it is not hard to check that $h_{\sigma}(\omega_{0})=0$. On the other hand, $\overline O(\omega_{0})=\Lambda_{2}$ and hence $h(\sigma\mid\overline O(\omega_{0}))=\log 2$.

At the same time we have obtained an example of a trajectory that is quasi-random in the sense of Alekseev \cite{1} and yet deterministic.

For any trajectory of a strictly ergodic DS,
\[
h(T\mid\overline O(x))=h_{T}(x)=h(T).
\]

In conclusion we note that the notion of a $\mu$-regular point first appeared and is used fruitfully in number theory. An ergodic treatment of a number of problems in analytic number theory can be found in the monograph of A.~G.~Postnikov \cite{13}.

\subsection*{4.3.~Algorithmic complexity of a trajectory}

\subsubsection*{4.3.1}

By the remark to Proposition~3.6,
\[
K(x,T)\le h(T\mid\overline O(x))
\]
for any $x\in X$, i.e.\ the complexity of a trajectory does not exceed its combinatorial entropy; this inequality can be strict (see Example 4.3.2 below). Thus, if a DS is not ``quasi-random'' in the sense of Alekseev (i.e.\ if $h(T)=0$), then the complexity of every trajectory equals zero.

In conclusion we note that in the case of a symbolic DS the complexity and combinatorial entropy are related by (A.~A.~Brudno, see \cite[Theorem 5.4]{1})
\[
h(\sigma\mid\overline O(\omega))=\limsup_{n\to\infty}(1/n) K((\sigma^{k}\omega)^{n}).
\]

\subsubsection*{4.3.2}

By Theorem~3.2 the complexity of a $\mu$-regular trajectory does not exceed the entropy with respect to the measure $\mu$, i.e.\ $K(x,T)\le h_{\mu}(T)$. We show that this inequality can be strict. Indeed, let
\[
\omega_{1}=0.1.01.10.11.000.\ldots,
\]
i.e.\ all finite binary words are written out in a row. It is well known that $\omega_{1}\in M_{m}$. Here $m$ is the uniform Bernoulli measure, hence $h_{\sigma}(\omega_{1})=\log 2$. On the other hand, it is not hard to construct a computable function $A_{0}$ that recovers the binary word $\omega_{1}^{n}$ from the number $n$. We obtain:
\[
K(\omega_{1})\le\lim_{n\to\infty}\frac{K_{A_{0}}(\omega_{1}^{n})}{n}\le\lim_{n\to\infty}\frac{\log n}{n}=0.
\]
Thus, there exist trajectories which are non-deterministic in the sense of Kamae with zero complexity, and the set $\overline X_{t}\setminus \overline W_{t}$ from Proposition~3.20 may be non-empty.

\subsubsection*{4.3.3}

A stronger result also holds. Since the construction of the sequence $\omega$ in the example of Grillenberger mentioned above is constructive, $K(\omega)=0$. By the arbitrariness of the choice of the number $h$ in this example we see that a trajectory need not be typical, in the sense of complexity, even for the strictly ergodic system it generates, and that the function $K(x,T)$ need not be constant on such a system.

It is appropriate to introduce the following

\begin{definition}
A point $x\in X$ will be called $\mu$-\emph{complex} if $\mu\in V_{T}(x)$ and $K(x,T)=h_{\mu}(T)$.
\end{definition}

\subsection*{4.4.~Complexity and randomness}

\subsubsection*{4.4.1}

Here we shall consider the connection of the notion of complexity of a trajectory, introduced in 4.3.2, with the notion of randomness in the sense of Martin-L\"of, generally accepted at present. We briefly dwell on the definition of this notion (considering, for simplicity, the space $\Lambda_{N}$).

A \emph{test} is a family of sets $c=\{C_{i}\}_{i\in\Zp}$ constructively describable and satisfying the conditions:
\begin{enumerate}
  \item $C_{0}\supseteq C_{1}\supseteq\ldots$;
  \item each $C_{i}$ is sequentially open;
  \item $\mu(C_{i})\le 2^{-i}$ for each $i\in\Zp$.
\end{enumerate}
The set $R_{c}=\bigcap_{i\in\Zp} C_{i}$ by definition consists of the sequences which do not pass the test $c$. In \cite{25} Martin-L\"of showed the existence of a universal test $c_{0}$ such that $R_{c}\subseteq R_{c_{0}}$ for any test $c$. Sequences $\omega\notin R$ are proposed to be called $\mu$-\emph{random}.

In \cite{11} it is shown that under some natural assumptions all probability-theoretic laws hold for sequences random in this sense. Therefore the equality $K(\omega)=h_{\mu}(\sigma)$ is (by Theorem~3.1) a necessary condition for randomness of $\omega$ with respect to the measure $\mu$. We show that this condition is not sufficient. Let $m$ be the uniform Bernoulli measure on $\Lambda_{2}$, and let the point $\omega_{0}$ be $m$-complex and $m$-random. Define a sequence $\widetilde\omega=\{\widetilde\omega(i)\}_{i\in\Zp}$ as follows:
\[
\widetilde\omega_{0}(i)=\begin{cases} 0, & \text{if}\ i=2^{k}\ (k=0,1,2,\ldots)\\ \omega_{0}(i), & \text{otherwise.}\end{cases}
\]
Obviously $V_{\sigma}(\widetilde\omega_{0})=V_{\sigma}(\omega_{0})$. Furthermore, let $A'=A'(p)$ be an a.\,opt.\,f.\ whose value on words $p=\bar p_{1}p_{2}$ is obtained by successively inserting the letters of the word $p_{1}$ into the word $A(p_{2})$ at the positions numbered $2^{i}$ ($i=1,2,\ldots,l(p_{1})$). Then for all $n$,
\[
K_{A'}(\widetilde\omega_{0}^{n})\le K_{A'}(\omega_{0}^{n})+2+2\log n.
\]
Therefore,
\[
K(\widetilde\omega_{0})\ge K(\omega_{0})=\log 2,\quad\text{i.e.}\quad K(\widetilde\omega_{0})=\log 2.
\]
Thus $\widetilde\omega_{0}$ is also $m$-complex. However, it is not difficult to verify that the family of sets
\[
c=\{C_{i}\}_{i\in\Zp},\quad\text{where}\ C_{i}=\{\omega\in\Lambda_{2}:\omega(2^{k})=0\ \text{for}\ k=0,1,\ldots,i-1\},
\]
is a test. Since the sequence $\widetilde\omega_{0}\in R_{c}$, it cannot be $m$-random.

\section*{Conclusion}

In contrast to the preceding material, the conclusion does not contain mathematically rigorous results. Its goal is to state, at an intuitive level, the author's attempt to find a general approach to the consideration of various characteristics of a dynamical system that are, in some degree, related to questions of complexity. The considerations adduced below, which may seem disputable, allow one to regard all results of the present work as a single whole, connecting the theory of algorithms with the theory of dynamical systems.

The main connecting link is the following

\medskip

\textbf{Thesis.} \emph{Every entropy characteristic of a dynamical system is some algorithmic function effecting the encoding of a finite segment of a trajectory of the dynamical system into a binary word. In so doing, the numerical expression of this characteristic is the asymptotics of the amount of information (measured in bits/symbol) necessary for recovering, with the aid of this function, any trajectory among one or another class of trajectories.}

\medskip

We give some considerations in support of this thesis (restricting ourselves --- which is not very essential --- to the case of a symbolic system).

In Proposition~1.12 a function constructed by Shannon is given which performs the encoding of $\mu$-almost any sufficiently long trajectory using $h_{\mu}(\sigma)$ bits/symbol. The restriction ``almost any'' here arises naturally from the insensitivity of the metric entropy to the behavior of the system on a set of measure zero. The second restriction --- on the length of the trajectory --- is an inevitable consequence of any algorithmic approach, since at fixed lengths one would have to take into account too many particularities which do not affect the asymptotic behavior.

In the general case (without restrictions on the measure) contained in Proposition~1.12, the same result is obtained if one uses the frequency-encoding function $A^{\ast}$ constructed in Lemma~1.9.

Thus, $h_{\mu}(\sigma)$ bits/symbol is the amount of information necessary and sufficient for recovering, by means of the function $A^{\ast}$, almost any trajectory of the DS $(\Omega,\sigma)$.

We turn now to topological entropy. The computable function (which we shall denote by $A^{T}$) constructed in the proof of Lemma~2 of \cite{3} allows one to assert in turn that the amount of information necessary and sufficient for recovering any trajectory of the system by means of the function $A^{T}$ is $h(T)$ bits/symbol.

It is clear that in the case of entropy characteristics of \emph{individual} trajectories one must recover only that trajectory itself. One can say that a simple modification of $A^{\ast}$ will lead us to the entropy of a point in the sense of Kamae (as is done, for example, in the proof of Theorem~3.2), and the combinatorial entropy of a trajectory is obtained by a certain transformation of the function $A^{T}$.

Finally, the very definition of algorithmic complexity of a trajectory corresponds to an asymptotically optimal function; Schnorr in \cite{16} showed how, following this idea but \emph{not} averaging over the length of the trajectory, one obtains sequences random in the sense of Martin-L\"of.

We can now explain the nature of Examples 4.2.2, 4.3.2 and 4.4.1. The first of them is an example of a dense trajectory with pathological statistical properties. Hence this trajectory, typical for the function $A^{T}$ and consequently quasi-random, is trivial from the point of view of the function $A^{\ast}$ and consequently deterministic (since $h_{\sigma}(\omega_{0})=0$).

The sequence $\omega_{1}$ in Example 4.3.2, by its statistical properties, does not differ from other regular sequences; therefore $h_{\sigma}(\omega_{1})=\log 2$ (non-determinacy). However it is describable if one knows binary arithmetic, and therefore its complexity with respect to an asymptotically optimal function equals zero. In Example 4.4.1 it is shown that averaging over the length of a trajectory, which does not affect the $\mu$-complexity of the trajectory, may affect its membership in the set of $\mu$-random trajectories.

\medskip

\noindent Received 1.XII.1978

\begin{thebibliography}{99}

\bibitem{1} Alekseev V.~M. \emph{Symbolic dynamics.} Trudy of the XI Summer Mathematical School. Institute of Mathematics, AN UkrSSR, Kiev, 1976.
\bibitem{2} Billingsley P. \emph{Ergodic theory and information.} Moscow: Mir, 1963.
\bibitem{3} Brudno A.~A. Topological entropy and complexity in the sense of A.~N.~Kolmogorov. --- Uspekhi Mat.~Nauk, 1974, 29, no.~6, 157--158.
\bibitem{4} Brudno A.~A. Symbolic dynamics and entropy. --- Uspekhi Mat.~Nauk, 1977, 32, no.~3, 180.
\bibitem{5} Brudno A.~A. On the complexity of trajectories of a dynamical system. --- Uspekhi Mat.~Nauk, 1978, 76, no.~1, 207--208.
\bibitem{6} Dinaburg E.~I. Connection between various entropy characteristics of dynamical systems. --- Izv. AN SSSR, Ser.\ Mat., 1971, 35, no.~2, 324--366.
\bibitem{7} Zvonkin A.~K., Levin L.~A. The complexity of finite objects and the foundations of the notions of information and randomness by means of the theory of algorithms. --- Uspekhi Mat.~Nauk, 1970, 25, no.~6, 85--127.
\bibitem{8} Katok A.~B., Sinai Ya.~G., Stepin A.~M. Theory of dynamical systems and general groups of transformations with invariant measure. --- In: Itogi Nauki, Mat. Analiz, vol.~13. Moscow, 1967, 129--262.
\bibitem{9} Kolmogorov A.~N. A new metric invariant of transitive automorphisms of Lebesgue spaces. --- Dokl. AN SSSR, 1958, 119, no.~5, 861--864.
\bibitem{10} Kolmogorov A.~N. Three approaches to the definition of the concept of ``amount of information''. --- Problemy Peredachi Informatsii, 1965, 5, no.~3, 3--7.
\bibitem{11} Levin L.~A. Laws of conservation (non-increase of information) and questions of the foundations of probability theory. --- Problemy Peredachi Informatsii, 1976, 74, no.~3, 30--35.
\bibitem{12} Oxtoby J. Ergodic sets. --- Uspekhi Mat.~Nauk, 1953, 8, no.~3, 75--97.
\bibitem{13} Postnikov A.~G. Ergodic problems in the theory of congruences and the theory of diophantine approximations. --- Trudy MIAN, vol.~82, Moscow, 1966.
\bibitem{14} Rokhlin V.~A. Lectures on the entropy theory of measure-preserving transformations. --- Uspekhi Mat.~Nauk, 1967, 22, no.~5, 3--56.
\bibitem{15} Shannon C. \emph{Papers on information theory and cybernetics.} Moscow: IL, 1963.
\bibitem{16} Schnorr C.~P. A unified approach to the definition of random sequences. --- In: Complexity of computations and algorithms. Moscow: Mir, 1974, 370--387.
\bibitem{17} Jacobs K. Machine-generated 0--1 sequences. --- In: Turing machines and recursive functions. Moscow: Mir, 1972, 216--247.
\bibitem{18} Adler R.~L., Konheim A.~G., McAndrew M.~H. Topological entropy. --- Trans. Amer. Math. Soc., 1967, 114, no.~2, 309--319.
\bibitem{19} Bowen R. Topological entropy for noncompact sets. --- Trans. Amer. Math. Soc., 1973, vol.~184, 125--136.
\bibitem{20} Denker M., Grillenberger C., Sigmund K. \emph{Ergodic theory on compact sets.} --- Lecture Notes in Mathematics, 527, 1976.
\bibitem{21} Furstenberg H. Disjointness in ergodic theory, minimal sets and a problem in diophantine approximation. --- Math. Syst. Theory, 1967, 1, 1--49.
\bibitem{22} Goodwyn L.~W. Comparing topological entropy with measure-theoretic entropy. --- Amer.\ J.~Math., 94, no.~2 (1972), 366--388.
\bibitem{23} Grillenberger C. Constructions of strictly ergodic systems, I. Given entropy. --- Z.\ Wahrscheinlichkeitstheorie und Verw.\ Geb., 1973, 25, no.~4, 323--334.
\bibitem{24} Kamae T. Normal numbers and ergodic theory. --- Lecture Notes in Mathematics, 550, 1976.
\bibitem{25} Martin-L\"of P. The definition of random sequences. --- Information and Control, 1966, 9, 619--682.
\bibitem{26} Morse M., Hedlund G.~A. Symbolic dynamics II, Sturmian trajectories. --- Amer.\ J.~Math., 1940, 62, no.~1, 1--42.

\end{thebibliography}

\end{document}
