Content-Type: multipart/mixed; boundary="-------------0210220710501" This is a multi-part message in MIME format. ---------------0210220710501 Content-Type: text/plain; name="02-431.keywords" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="02-431.keywords" chaoticity, complexity ---------------0210220710501 Content-Type: application/x-tex; name="complexity.tex" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="complexity.tex" \documentclass[aps,preprint,amssymb,amsmath,eqsecnum,nofootinbib]{revtex4} \newtheorem{question}{QUESTION}[section] \newtheorem{definition}{DEFINITION}[section] \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{conjecture}{Conjecture}[section] \newtheorem{remark}{Remark}[section] \newtheorem{axiom}{AXIOM}[section] \newtheorem{constraint}{CONSTRAINT}[section] \newtheorem{diagram}{DIAGRAM}[section] \newenvironment{hypothesis}{HP: \begin{center}} {\end{center}} \newenvironment{thesis}{TH: \begin{center}} {\end{center}} \newenvironment{proof}{\begin{center}PROOF: \end{center}} {$ \blacksquare $} \newtheorem{example}{Example}[section] \begin{document} \title{The information-theoretical viewpoint on the physical complexity of classical and quantum objects and their dynamical evolution} \author{Gavriel Segre} \homepage{http://www.gavrielsegre.com} \email{info@gavrielsegre.com} \begin{abstract} Charles Bennett's measure of physical complexity for classical objects, namely logical-depth, is used in order to prove that a chaotic classical dynamical system is not physical complex. The natural measure of physical complexity for quantum objects, quantum logical-depth, is then introduced in order to prove that a chaotic quantum dynamical system is not physical complex too. \end{abstract} \maketitle \newpage \tableofcontents \newpage \section{Notation} \bigskip \begin{tabular}{|c|c|} % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... $ \forall $ & for all (universal quantificator) \\ $ \exists $ & exist (existential quantificator) \\ $ \exists \; ! $ & exist and is unique \\ $ x \; = \; y $ & x is equal to y \\ $ x \; := \; y $ & x is defined as y \\ $ \Sigma $ & binary alphabet $ \{ 0 , 1 \} $ \\ $ \Sigma_{n} $ & n-letters' alphabet \\ $ \Sigma^{\star} $ & strings on the alphabet $ \Sigma $ \\ $ \Sigma^{\infty} $ & sequences on the alphabet $ \Sigma $ \\ $ \vec{x} $ & string \\ $ | \vec{x} | $ & length of the string $ \vec{x} $ \\ $ <_{l} $ & lexicographical ordering on $ \Sigma^{\star} $ \\ $ string(n) $ & $ n^{th} $ string in lexicographic order \\ $ \bar{x} $ & sequence \\ $ \cdot $ & concatenation operator \\ $ x_{n} $ & $ n^{th} $ digit of the string $\vec{x} $ or of the sequence $ \bar{x} $ \\ $ \vec{x}(n) $ & prefix of length n of the string $ \vec{x} $ or of the sequence $ \bar{x} $ \\ $ \vec{x}^{\star} $ & canonical string of the string $ \vec{x}$ \\ $ K( \vec{x} ) $ & plain Kolmogorov complexity of the string $ \vec{x} $ \\ $ I( \vec{x} ) $ & algorithmic information of the string $ \vec{x} $ \\ $ U( \vec{x} ) \downarrow $ & U halts on input $ \vec{x} $ \\ $ D_{s} ( \vec{x} ) $ & logical-depth of $ \vec{x} $ at significance level s \\ $ t-DEEP( \Sigma^{\star} ) $ & t-deep strings of cbits \\ $ t-SHALLOW ( \Sigma^{\star} ) $ & t-shallow strings of cbits \\ $ REC-MAP ( \Sigma^{\star} \, , \, \Sigma^{\star} ) $ & (total) recursive functions over $ \Sigma^{\star} $ \\ $ \leq_{T} $ & Turing reducibility \\ $ \leq_{T}^{P} $ & polynomial time Turing reducibility \\ $ \leq_{tt} $ & truth-table reducibility \\ $ CHAITIN-RANDOM (\Sigma^{\infty} ) $ & Martin L\"{o}f - Solovay - Chaitin random sequences of cbits \\ $ HALTING( \mu ) $ & halting set of the measure $ \mu $ \\ \hline \end{tabular} \newpage \begin{footnotesize} \begin{tabular}{|c|c|} $ \mu_{Lebesgue} $ & Lebesgue measure \\ $ \mu-RANDOM( \Sigma^{\infty} ) $ & Martin L\"{o}f random sequences of cbits w.r.t. $ \mu $ \\ $ B( \bar{x} ) $ & Brudno algorithmic entropy of the sequence $ \bar{x} $ \\ $ BRUDNO (\Sigma^{\infty} ) $ & Brudno random sequences of cbits \\ $ STRONGLY-DEEP (\Sigma^{\infty} ) $ & strongly-deep sequences of cbits \\ $ STRONGLY-SHALLOW (\Sigma^{\infty} ) $ & strongly-shallow sequences of cbits \\ $ WEAKLY-DEEP (\Sigma^{\infty} ) $ & weakly-deep sequences of cbits \\ $ WEAKLY-SHALLOW (\Sigma^{\infty} ) $ & weakly-shallow sequences of cbits \\ $ {\mathcal{P}} ( X \, , \, \mu ) $ & (finite, measurable) partitions of $ ( X \, , \, \mu ) $ \\ $ \preceq $ & coarse-graining relation on partitions \\ $ A \bigvee B $ & coarsest refinement of A and B \\ $ h_{CDS} $ & Kolmogorov-Sinai entropy of CDS \\ $ \psi_{A} $ & symbolic translator w.r.t. A \\ $ \psi_{A}^{(k)} $ & k-point symbolic translator w.r.t. A \\ $ \psi_{A}^{(\infty)} $ & orbit symbolic translator w.r.t. A \\ $ \Psi $ & universal symbolic translator \\ $ \Psi^{(k) } $ & k-point universal symbolic translator \\ $ \Psi^{(\infty)} $ & orbit universal symbolic translator \\ $ B_{CDS} (x) $ & Brudno algorithmic entropy of x's orbit in CDS \\ $ H(P) $ & Shannon's entropy of the distribution P \\ $ L_{D,P} $ & average code-word length w.r.t. the code D and the distribution P \\ $ L_{P} $ & minimal average code-word length w.r.t. the distribution P \\ $ {\mathcal{H}}_{2} $ & one-qubit Hilbert space \\ $ {\mathcal{H}}_{2}^{\bigotimes n} $ & n-qubits Hilbert space \\ $ {\mathcal{E}}_{n} $ & computational basis of $ {\mathcal{H}}_{2}^{\bigotimes n} $ \\ $ {\mathcal{H}}_{2}^{\bigotimes \star} $ & Hilbert space of qubits' string \\ $ {\mathcal{E}}_{\star} $ & computational basis of $ {\mathcal{H}}_{2}^{\bigotimes \star} $ \\ $ {\mathcal{H}}_{2}^{\bigotimes \infty } $ & Hilbert space of qubits' sequences \\ $ {\mathcal{E}}_{\infty} $ & computational rigged-basis of $ {\mathcal{H}}_{2}^{\bigotimes \infty} $ \\ $ {\mathcal{B}} ( {\mathcal{H}} ) $ & bounded linear operators on $ {\mathcal{H}} $ \\ \hline \end{tabular} \end{footnotesize} \newpage \begin{tabular}{|c|c|} $ | \psi >^{\star} $ & canonical program of $ | \psi > $ \\ $ D_{s} ( | \psi > ) $ & logical depth of $ | \psi > $ at significance level s \\ $ t-DEEP( {\mathcal{H}}_{2}^{\bigotimes \star} ) $ & t-deep strings of qubits \\ $ t-SHALLOW( {\mathcal{H}}_{2}^{\bigotimes \star} ) $ & t-shallow strings of qubits \\ $ S(A) $ & states over the noncommutative space A \\ $ card (A) $ & cardinality of A \\ $ INN(A) $ & inner automorphisms of A \\ $ card_{NC} (A) $ & noncomutative cardinality of A \\ $ \tau_{unbiased} $ & unbiased noncommutative probability distribution \\ $ \Sigma_{NC}^{\infty} $ & noncommutative space of qubits' sequences \\ R & hyperfinite $ II_{1} $ factor \\ $ RANDOM ( \Sigma_{NC}^{\infty} ) $ & random sequences of qubits \\ $ \leq_{tt}^{Q} $ & quantum truth-table reducibility \\ $ WEAKLY-DEEP (\Sigma_{NC}^{\infty} ) $ & weakly-deep sequences of qubits \\ $ WEAKLY-SHALLOW (\Sigma_{NC}^{\infty} ) $ & weakly-shallow sequences of qubits \\ $ {\mathcal{L}}_{RANDOMNESS}^{NC} ( A , \omega ) $ & laws of randomness of $ ( A \, , \, \omega ) $ \\ $ \omega - RANDOM ( \Sigma_{NC}^{\infty} ) $ & random sequences of qubits w.r.t. $ \omega $ \\ $ h_{d.e.} (QDS) $ & dynamical entropy of the quantum dynamical system QDS \\ i.e. & id est \\ e.g. & exempli gratia \\ \hline \end{tabular} \newpage \section{The shallowness of random objects} \label{sec:The shallowness of random objects} Despite denoting it with the term \emph{"complexity"}, Andre\v{i} Nikolaevich Kolmogorov \cite{Kolmogorov-65}, \cite{Kolmogorov-69}, \cite{Kolmogorov-83a}, \cite{Kolmogorov-83b}, \cite{AMS-LMS-00} introduced the notion denoted nowadays by the school of Paul Vitanyi \cite{Li-Vitanyi-97} as \emph{"plain-Kolmogorov-complexity"} (that I will denote with the letter K from here and beyond) in order of obtaining an intrinsic measure of the \emph{amount of information} of that object and not as a measure of the \emph{amount of physical-complexity} of that object. That the \emph{amount of information} and the \emph{amount of physical complexity} of an object are two completely different concepts became furtherly clear after the introduction by Gregory Joseph Chaitin of the notion denoted nowadays by the school of Paul Vitanyi \cite{Li-Vitanyi-97} as \emph{"prefix-Kolmogorov-complexity"} and denoted by the school of Chaitin and Cristian S. Calude simply as \emph{algorithmic information} \cite{Calude-02} (and that I will denote with the letter I from here and beyond) and the notion of algorithmic-randomness it gives rise to: an algorithmically random object has a very high algorithmic information but is certainly not physically-complex. Such a simple consideration is indeed sufficient to infer that \emph{algorithmic information} can be seen in no way as a measure of physical complexity. A natural measure of physical complexity within the framework of Algorithmic Information Theory, the \emph{logical depth}, was later introduced by Gregory Chaitin and Charles Bennett \cite{Bennett-88}, constituing what is nowadays generally considered as the \emph{algorithmic information theoretic viewpoint} as to physical complexity, nor even taking in consideration the new-age folklore of some author \cite{Boffetta-Cencini-Falcioni-Vulpiani-01} that, not only ignores that, as it was clearly realized by Brudno himself \cite{Brudno-78}, \cite{Brudno-83}, \cite{Segre-02}, the \emph{chaoticity} of a dynamical system (defined as the strict positivity of its Kolmogorov-Sinai entropy) is equivalent to its \emph{weak algorithmic chaoticity} (defined as the condition that almost all the trajectories, simbolically codified, are \emph{Brudno-algorithmically random}) but is weaker than its \emph{strong algorithmic chaoticity} (defined as the condition that almost all the trajectories, simbolically codified, are \emph{Martin-L\"{o}f-Solovay-Chaitin-algorithmically random}), but uses the notions of \emph{chaoticity} and \emph{complexity} as if they were sinonymous, a thing obviously false since, as we have seen, the (weak) algorithmic randomness of almost all the trajectories of a chaotic dynamical system implies exactly the opposite, namely that its trajectories are not \emph{complex} at all. Indeed it is natural to define \emph{complex} a dynamical system such that almost all its trajectories, simbolically codified, are \emph{logical deep}. So, despite the common naive folklore of some author belonging to "new age fashion of complexity" used to adopt the terms "\emph{chaoticity}" and " \emph{complexity}" as interchangable, one has that that every chaotical dynamical system is shallow, as I will extensively discuss. The key point of such an issue is so important to deserve a further repetition with the own words of Charles Bennett \cite{Bennett-88} illustrating the physical meaning of the notion of \emph{logical depth} and the reason why it is a good measure of physical complexity: \begin{center} \textit{"The notion of logical-depth developed in the present paper was first described in \cite{Chaitin-77}, and at greater length in \cite{Bennett-82} and \cite{Bennett-85}; similar notions have been independently introduced by \cite{Adleman-79} ("potential"), \cite{Levin-Vjugin-77} ("incomplete sequence"), \cite{Levin-84} ("hitting time") and Koppel, this volume ("sophistication"). See also Wolfram's work on "computational irreducibility" \cite{Wolfram-85} and Hartmanis' work on time- and space-bounded algorithmic information \cite{Hartmanis-83}} \end{center} \begin{center} \textit{"We propose depth as a formal measure of value. From the earliest days of information theory it has been appreciated that information per se is not a good measure of message value. For example a typical sequence of coin tosses has high information content but little value; an ephemeresis, giving the positions of the moon and planets every day for a hundred years, has no more information than the equations of motions and initial conditions from which it was calculated, but saves its owner the effort of recalculating these positions. The value of a message thus appears to reside not in its information (its absolutely unpredictable parts), nor in its obvious redudancy (verbatim repetitions, unequal digit frequencies), but rather in what might be called its buried redudancy - parts predictable only with difficulty, things the receiver could in principle have figured out without being told, but only at considerable cost in money, time or computation. In other words the value of a message is the amount of mathematical or other work plausibly done by its originator, which its receiver is saved from having to repeat"} \end{center} \newpage \section{The physical complexity of strings and sequences of cbits} I will follow from here and beyond the notation of my Phd-thesis \cite{Segre-02}; conseguentially, given the binary alphabet $ \Sigma \, := \, \{ 0 \ , , \, 1 \} $, I will denote by $ \Sigma^{\star} $ the set of all the strings on $ \Sigma $ (i.e. the set of all the strings of cbits), by $ \Sigma^{\infty} $ the set of all the sequences on $ \Sigma $ (i.e. the set of all the sequences of cbits) and by $ CHAITIN-RANDOM ( \Sigma^{\infty} )$ its subset consisting of all the Martin-L\"{o}f-Solovay-Chaitin random sequences of cbits. I will furthermore denote strings by an upper arrow and sequences by an upper bar, so that I will talk about the string $ \vec{x} \in \Sigma^{\star} $ and the sequence $ \bar{x} \in \Sigma^{\infty}$; $ | \vec{x} | $ will denote the length of the string $ \vec{x} $, $ x_{n} $ will denote the $ n^{th}$-digit of the string $ \vec{x} $ or of the sequence $ \bar{x}$ while $ \vec{x}_{n} $ will denote its prefix of length n. I will, finally, denote by $ <_{l}$ the lexicographical-ordering relation over $ \Sigma^{\star} $ and by string(n) the $ n^{th} $ string in such an ordering. Fixed once and for all a universal Chaitin computer U, let us recall the following basic notions: given a string $ \vec{x} \in \Sigma^{\star} $ and a natural number $ n \in { \mathbb{N}} $: \begin{definition} \label{def:canonical program of a string} \end{definition} CANONICAL PROGRAM OF $ \vec{x} $: \begin{equation} \vec{x}^{\star} \; := \; \min_{<_{l}} \min_{| \cdot | } \{ \vec{y} \in \Sigma^{\star} \, : \, U( \vec{y} ) = \vec{x} \} \end{equation} \begin{definition} \end{definition} $ \vec{x}$ IS n-COMPRESSIBLE: \begin{equation} | \vec{x}^{\star} | \; \leq \; | \vec{x} | \, - \, n \end{equation} \begin{definition} \end{definition} $ \vec{x}$ IS n-INCOMPRESSIBLE: \begin{equation} | \vec{x}^{\star} | \; > \; | \vec{x} | \, - \, n \end{equation} \begin{definition} \end{definition} HALTING TIME OF THE COMPUTATION WITH INPUT $ \vec{x} $: \begin{equation} T( \vec{x} ) \; := \; \left\{% \begin{array}{ll} \text{number of computational steps after which U halts on input $ \vec{x} $ }, & \hbox{if $ U(\vec{x}) = \downarrow$} \\ + \infty, & \hbox{otherwise.} \\ \end{array}% \right. \end{equation} We have at last all the ingredients required to introduce the notion of \emph{logical depth} as to strings. Given a string $ \vec{x} \in \Sigma^{\star} $ and two natural number $ s , t \in {\mathbb{N}} $: \begin{definition} \label{def:logical depth of a string of cbits} \end{definition} LOGICAL DEPTH OF $ \vec{x} $ AT SIGNIFICANCE LEVEL s: \begin{equation} D_{s}( \vec{x} ) \; := \; \min \{ T( \vec{y} ) \, : \, U( \vec{y} ) \, = \, \vec{x} \, , \, \vec{y} \text{ s-incompressible } \} \end{equation} \begin{definition} \end{definition} $ \vec{x} $ IS t-DEEP AT SIGNIFICANCE LEVEL s: \begin{equation} D_{s}( \vec{x} ) \; > \; t \end{equation} \begin{definition} \end{definition} $ \vec{x} $ IS t-SHALLOW AT SIGNIFICANCE LEVEL s: \begin{equation} D_{s}( \vec{x} ) \; \leq \; t \end{equation} I will denote the set of all the t-deep strings as $ t-DEEP( \Sigma^{\star} ) $ and the set of all the t-shallow sequences as $ t-SHALLOW( \Sigma^{\star} ) $ . Exactly as it is impossible to give a sharp distinction among \emph{Chaitin-random} and \emph{regular} strings while it is possible to give a sharp distinction among \emph{Martin-L\"{o}f-Solovay-Chaitin-random} and \emph{regular} sequences, it is impossible to give a sharp distinction among \emph{deep} and \emph{shallow} strings while it is possible to give a sharp distinction among \emph{deep} and \emph{shallow} sequences. Given a sequence $ \bar{x} \in \Sigma^{\infty} $: \begin{definition} \label{def:strongly-deep sequence of cbits} \end{definition} $ \bar{x} $ IS STRONGLY-DEEP: \begin{equation} card \{ n \in {\mathbb{N}} \, : \, D_{s}( \vec{x}(n) ) > f(n) \} \; < \; \aleph_{0} \; \; \forall s \in {\mathbb{N}} \, , \, \forall f \in REC-MAP ( \Sigma^{\star} , \Sigma^{\star} ) \end{equation} where, following once more the notation adopted in \cite{Segre-02}, $ REC-MAP ( \Sigma^{\star} , \Sigma^{\star} ) $ denotes the set of all the (total) recursive functions over $ \Sigma^{\star} $. To introduce a weaker notion of depth it is necessary to fix the notation as to reducibilities and degrees: denoted the \emph{Turing reducibility} by $ \leq_{T} $ and the polynomial time Turing reducibility by $ \leq_{T}^{P} $ \cite{Odifreddi-89} let us recall that there exist an intermediate constrained-reducibility among them: the one, called \emph{recursive time bound reducibility}, in which the halting-time is constrained to be not necessarily a polynomial but a generic recursive function; since \emph{recursive time bound reducibility} may be proved to be equivalent to \emph{truth-table reducibility} (I demand to \cite{Odifreddi-99a},\cite{Calude-02} for its definition and for the proof of the equivalence) I will denote it by $ \leq_{tt} $. A celebrated theorem proved by Peter Gacs in 1986 \cite{Gacs-86} states that every sequence is computable by a Martin-L\"{o}f-Solovay-Chaitin-random sequence: \begin{theorem} \end{theorem} GACS' THEOREM: \begin{equation} \bar{x} \; \leq_{T} \; \bar{y} \; \; \forall \bar{x} \in \Sigma^{\infty} \, , \, \forall \bar{y} \in CHAITIN-RANDOM (\Sigma^{\infty} ) \end{equation} This is no more true, anyway, if one add the constraint of recursive time bound, leading to the following: \begin{definition} \label{def:weakly-deep sequence of cbits} \end{definition} $ \bar{x} $ IS WEAKLY-DEEP: \begin{equation} \exists \bar{y} \in CHAITIN-RANDOM (\Sigma^{\infty} ) \, : \, \bar{x} \; >_{tt} \; \bar{y} \end{equation} I will denote the set of all the strongly-deep binary sequences by $ STRONGLY-DEEP(\Sigma^{\infty} ) $ and the set of all the weakly-deep binary sequences as $ WEAKLY-DEEP(\Sigma^{\infty}) $. Shallowness is then once more defined as the opposite of deepness: \begin{definition} \end{definition} STRONGLY-SHALLOW SEQUENCES OF CBITS: \begin{equation} STRONGLY-SHALLOW(\Sigma^{\infty} ) \; := \; \Sigma^{\infty} \, - \, STRONGLY-DEEP(\Sigma^{\infty} ) \end{equation} \begin{definition} \end{definition} WEAKLY-SHALLOW SEQUENCES OF CBITS: \begin{equation} WEAKLY-SHALLOW(\Sigma^{\infty} ) \; := \; \Sigma^{\infty} \, - \, WEAKLY-DEEP(\Sigma^{\infty} ) \end{equation} Weakly-shallow sequences of cbits may also be characterized in the following useful way \cite{Bennett-88}: \begin{theorem} \label{th:alternative characterization of weakly-shallow sequences of cbits} \end{theorem} ALTERNATIVE CHARACTERIZATION OF WEAKLY-SHALLOW SEQUENCES OF CBITS: \begin{equation} \bar{x} \in WEAKLY-SHALLOW(\Sigma^{\infty} )) \; \Leftrightarrow \; \exists \mu \, recursive \; : \; \bar{x} \in \mu-RANDOM( \Sigma^{ \infty }) \end{equation} where, following once more the notation of \cite{Segre-02}, $ \mu-RANDOM( \Sigma^{ \infty} ) $ denotes the set of all the Martin-L\"{o}f random sequences w.r.t. the measure $ \mu $. As to sequences of cbits, the considerations made in section\ref{sec:The shallowness of random objects} may be thoroughly formalized through the following: \begin{theorem} \label{th:weak-shallowness of random sequences of cbits} \end{theorem} WEAK-SHALLOWNESS OF MARTIN L\"{O}F-SOLOVAY-CHAITIN RANDOM SEQUENCES \begin{equation} CHAITIN-RANDOM( \Sigma^{ \infty} ) \, \cap \, WEAKLY-DEEP(\Sigma^{\infty}) \; = \; \emptyset \end{equation} \begin{proof} Since the Lebesgue measure $ \mu_{Lebesgue} $ is recursive and by definition: \begin{equation} CHAITIN-RANDOM( \Sigma^{ \infty} ) \; = \; \mu_{Lebesgue} - RANDOM( \Sigma^{ \infty} ) \end{equation} the thesis immediately follows by theorem\ref{th:alternative characterization of weakly-shallow sequences of cbits} \end{proof} \newpage \section{The physical complexity of classical dynamical systems} \label{sec:The physical complexity of classical dynamical systems} Since much of the new-age folklore about complexity is based on a spread confusion among different notions, starting from the basic difference among \emph{plain Kolmogorov complexity} K and \emph{algorithmic information} I, an intellectually honest analysis requires a lot of care. Let us start from the following notions by Brudno: \begin{definition} \label{def:Brudno algorithmic information of a sequence} \end{definition} BRUDNO ALGORITHMIC ENTROPY OF $ \bar{x} \in \Sigma^{\infty} $: \begin{equation} B( \bar{x} ) \; := \; \lim_{n \rightarrow \infty} \frac{K( \vec{x}(n)) }{n} \end{equation} \smallskip At this point one could think that considering the asympotic rate of \emph{algorithmic information} instead of \emph{plain Kolmogorov complexity} would result in a different definition of the algorithmic entropy of a sequence. That this is not the case is the content of the following: \begin{theorem} \label{th:plain-prefix insensitivity of Brudno algorithmic entropy} \end{theorem} \begin{equation} B( \bar{x} ) \; = \; \lim_{n \rightarrow \infty} \frac{I( \vec{x}(n))}{n} \end{equation} \begin{proof} It immediately follows by the fact that \cite{Staiger-99}: \begin{equation} I( \vec{x}(n) ) \, - \, K( \vec{x}(n) ) \; = \; o(n) \end{equation} \end{proof} \begin{definition} \label{def:Brudno random sequence} \end{definition} $ \bar{x} \in \Sigma^{\infty} $ IS BRUDNO RANDOM: \begin{equation} B( \bar{x} ) \; > \; 0 \end{equation} I will denote the set of all the Brudno random binary sequences by $ BRUDNO( \Sigma^{\infty}) $. One of greatest sources of confusion in the mentioned naive folklore arises from the ignorance of the following basic result proved by Brudno himself \cite{Brudno-78}: \begin{theorem} \label{th:Brudno randomness is weaker than Chaitin randomness} \end{theorem} BRUDNO RANDOMNESS IS WEAKER THAN CHAITIN RANDOMNESS: \begin{equation} BRUDNO-RANDOM( \Sigma^{\infty}) \; \subset \; CHAITIN -RANDOM(\Sigma^{\infty}) \end{equation} as we will see in the sequel of this section. Following the analysis performed in \cite{Segre-02} (to which I demand for further details) I will recall here some basic notion of Classical Ergodic Theory: given a classical probability space $ ( X \, , \, \mu ) $: \begin{definition} \label{def:endomorphism of a classical probability space} \end{definition} ENDOMORPHISM OF $ ( X \, , \, \mu ) $: $T \, : \, HALTING(\mu) \rightarrow HALTING(\mu) $ surjective : \begin{equation} \mu ( A ) \; = \; \mu ( T^{-1} A ) \; \; \forall A \in HALTING(\mu) \end{equation} where $ HALTING(\mu) $ is the halting-set of the measure $ \mu $, namely the $ \sigma$-algebra of subsets of X on which $ \mu $ is defined. \begin{definition} \label{def:automorphism of a classical probability space} \end{definition} AUTOMORPHISM OF $ ( X \, , \, \mu ) $: $T \, : \, HALTING(\mu) \rightarrow HALTING(\mu) $ injective endomorphism of $ ( X \, , \, \mu ) $ \begin{definition} \label{def:classical dynamical system} \end{definition} CLASSICAL DYNAMICAL SYSTEM: a triple $ ( X \, , \, \mu \, , \, T ) $ such that: \begin{itemize} \item $ ( X \, , \, \mu ) $ is a classical probability space \item $T \, : \, HALTING(\mu) \rightarrow HALTING(\mu) $ is an endomorphism of $ ( X \, , \, \mu ) $ \end{itemize} Given a classical dynamical system $ ( X \, , \, \mu \, , \, T ) $: \begin{definition} \label{def:reversible classical dynamical system} \end{definition} $ ( X \, , \, \mu \, , \, T ) $ IS REVERSIBLE: T is an automorphism \smallskip \begin{definition} \label{def:ergodic classical dynamical system} \end{definition} $ ( X \, , \, \mu \, , \, T ) $ IS ERGODIC: \begin{equation} lim_{n \rightarrow \infty} \frac{1}{n} \sum_{k=0}^{n-1} \, \mu ( A \cap T^{k}(B)) \; = \; \mu(A) \, \mu(B) \; \forall \, A,B \in HALTING( \mu ) \end{equation} \begin{definition} \label{def:mixing classical dynamical system} \end{definition} $ ( X \, , \, \mu \, , \, T ) $ IS MIXING: \begin{equation} lim_{n \rightarrow \infty} \, \mu ( A \cap T^{n}(B)) \; = \; \mu(A) \, \mu(B) \; \forall \, A,B \in HALTING( \mu ) \end{equation} Given a classical probability space $ ( X \, , \mu ) $: \begin{definition} \label{def:partition of a classical probability space} \end{definition} FINITE MEASURABLE PARTITION OF $ ( X \, , \, \mu ) $: \begin{equation} \begin{split} A \, & = \; \{ \, A_{1} \, , \, \cdots \, A_{n} \} \; n \in {\mathbb{N}} \, : \\ A_{i} & \in HALTING(\mu) \; \; i \, = \, 1 \, , \, \cdots \, , \, n \\ A_{i} & \, \cap \, A_{j} \, = \, \emptyset \; \; \forall \, i \, \neq \, j \\ \mu & ( \, X \,- \, \cup_{i=1}^{n} A_{i} \, ) \; = \; 0 \end{split} \end{equation} I will denote the set of all the finite measurable partitions of $ ( X \, , \, \mu ) $ by $ \mathcal{P} ( \, X \, , \, \mu \, ) $. Given two partitions $ A = \{ A_{i} \}_{i=1}^{n} \, , \, B = \{ B_{j} \}_{j=1}^{m} \; \in \; \mathcal{P} ( X , \mu ) $: \begin{definition} \end{definition} A IS A COARSE-GRAINING OF B $ (A \preceq B) $: every atom of A is the union of atoms by B \smallskip \begin{definition} \end{definition} COARSEST REFINEMENT OF $ A = \{ A_{i} \}_{i=1}^{n} $ AND $ B = \{ B_{j} \}_{j=1}^{m} \in {\mathcal{P}}( \; X \, , \mu \; ) $: \begin{equation} \begin{split} A \, & \vee \, B \; \in {\mathcal{P}}( X , \mu ) \\ A \, & \vee \, B \; := \; \{ \, A_{i} \, \cap \, B_{j} \, \; i =1 , \cdots , n \; j = 1 , \cdots , m \} \end{split} \end{equation} Clearly $ \mathcal{P} ( X , \mu ) $ is closed both under coarsest refinements and under endomorphisms of $ ( X , \mu ) $. Let us observe that, beside its abstract, mathematical formalization, the definition\ref{def:partition of a classical probability space} has a precise operational meaning. Given the classical probability space $ ( X , \mu ) $ let us suppose to make an experiment on the probabilistic universe it describes using an instrument whose resolutive power is limited in that it is not able to distinguish events belonging to the same atom of a partition $ A = \{ A_{i} \}_{i=1}^{n} \in \mathcal{P} ( X , \mu ) $. Consequentially the outcome of such an experiment will be a number \begin{equation} r \in \{ 1 , \cdots , n \} \end{equation} specifying the observed atom $ A_{r} $ in our coarse-grained observation of $ ( X, \mu ) $. I will call such an experiment an \emph{operational observation of $ ( X , \mu ) $ through the partition A}. Considered another partition $ B = \{ B_{j} \}_{i=1}^{n} \in \mathcal{P} ( X , \mu ) $ we have obviously that the operational observation of $ ( X , \mu ) $ through the partition $ A \vee B $ is the conjuction of the two experiments consisting in the operational observations of $ ( X , \mu ) $ through the partitions, respectively, A and B. Conseguentially we may consistentely call an \emph{operational observation of $ ( X , \mu ) $ through the partition A} more simply an \textbf{A-experiment}. The experimental outcome of an operational observation of $ ( X , \mu ) $ through the partition $ A = \{ A_{i} \}_{i=1}^{n} \in \mathcal{P} ( X , \mu ) $ is a classical random variable having as distribution the stochastic vector $ ( \begin{pmatrix} \mu(A _{1} ) \\ \vdots \\ \mu(A _{n}) \end{pmatrix} $ whose \emph{classical probabilistic information}, i.e. its Shannon entropy, I will call the entropy of the partition A, according to the following: \begin{definition} \end{definition} ENTROPY OF $ A = \{ A_{i} \}_{i=1}^{n} \in \mathcal{P} ( X , \mu ) $: \begin{equation} H(A) := H ( \begin{pmatrix} \mu ( A _{1} ) \\ \vdots \\ \mu ( A _{n} ) \ \end{pmatrix} ) \end{equation} It is fundamental, at this point, to observe that, given an experiment, one has to distinguish between two conceptually different concepts: \begin{enumerate} \item the \emph{uncertainty of the experiment}, i.e. the amount of uncertainty on the outcome of the experiment before of realizing it \item the \emph{information of the experiment}, i.e. the amount of information gained by the outcome of the experiment \end{enumerate} As lucidly observed by Patrick Billingsley \cite{Billingsley-65}, the fact that in Classical Probabilistic Information Theory both these concepts are quantified by the Shannon entropy of the experiment is a consequence of the following: \begin{theorem} \label{th:the soul of Classical Information Theory} \end{theorem} THE SOUL OF CLASSICAL INFORMATION THEORY \begin{equation} \text{information gained} \; = \; \text{uncertainty removed} \end{equation} \smallskip Theorem\ref{th:the soul of Classical Information Theory} applies, in particular, as to the partition-experiments we are discussing. \medskip Let us now consider a classical dynamical system $ CDS \, := \, ( X \, , \, \mu \, , \, T ) $. The T-invariance of $ \mu $ implies that the partitions $ A = \{ A_{i} \}_{i=1}^{n} \in \mathcal{P} ( X , \mu ) $ and $ T^{-1}A $ have equal probabilistic structure. Conseguentially the \emph{A-experiment} and the \emph{ $T^{-1}A $-experiment} are replicas, \emph{not necessarily independent}, of the same experiment, made at successive times. In the same way the \emph{$ \vee_{k=0}^{n-1} \, T^{-k} A $-experiment} is the compound experiment consisting in n replications $ A \, , \, T^{-1} A \, , \, , \cdots , \, T^{-(n-1)}A $ of the experiment corresponding to $ A \in {\mathcal{P}}(X , \mu) $. The amount of classical information per replication we obtain in this compound experiment is clearly: \begin{equation*} \frac{1}{n} \, H(\vee_{k=0}^{n-1} \, T^{-k} A ) \end{equation*} It may be proved \cite{Kornfeld-Sinai-00} that when n grows this amount of classical information acquired for replication converges, so that the following quantity: \begin{equation} h( A , T ) \; \:= \; lim_{n \rightarrow \infty} \, \frac{1}{n} \, H(\vee_{k=0}^{n-1} \, T^{-k} A ) \end{equation} does exist. In different words, we can say that $ h( A , T ) $ gives the asymptotic rate of acquired classical information by replication of the A-experiment. We can at last introduce the following fundamental notion \cite{Kolmogorov-58}, \cite{AMS-LMS-00}, \cite{Sinai-76}, \cite{Sinai-94}, \cite{Kornfeld-Sinai-00}: \begin{definition} \label{def:Kolmogorov-Sinai entropy} \end{definition} \begin{equation} h_{CDS} \; := \; sup_{A \in {\mathcal{P}}(X , \mu)} \, h( A , T ) \end{equation} By definition we have clearly that: \begin{equation} h_{CDS} \; \geq \; 0 \end{equation} \begin{definition} \label{def:classical chaoticity} \end{definition} CDS IS CHAOTIC: \begin{equation} h_{CDS} \; > \; 0 \end{equation} Definition\ref{def:classical chaoticity} shows explicitly that the concept of classical-chaos is an information-theoretic one: a classical dynamical system is chaotic if there exist at least one experiment on the system that, no matter how many times we insist on repeating it, continue to give us classical information. That such a meaning of classical chaoticity is equivalent to the more popular one as the sensible (i.e. exponential) dependence of dynamics from the initial conditions (the so called \emph{butterfly effect} for which the little perturbation of the atmospheric flow produced here by a butterfly's flight may produce an hurricane in Alaska) is a conseguence of Pesin's Theorem stating (under mild assumptions) the equality of the Kolmogorov-Sinai entropy and the sum of the positive Lyapunov exponents. This inter-relation may be caught observing that: \begin{itemize} \item if the system is chaotic we know that there exist an experiment whose repetition definitely continues to give information: such an information may be seen as the information on the initial condition that is necessary to furnish more and more with time if one want to keep the error on the prediction of the phase-point below a certain bound \item if the system is not chaotic the repetition of every experiment is useful only a finite number of times, after which every suppletive repetition doesn't furnish further information \end{itemize} Let us now consider the issue of symbolically translating the coarse-grained dynamics: the traditional way of proceeding is that described in the second section of \cite{Alekseev-Yakobson-1981}: given a positive integer $ n \in {\mathbb{N}} $ let us introduce the: \begin{definition} \end{definition} n-LETTERS ALPHABET: \begin{equation} \Sigma_{n} \; := \; \{ 0 , \cdots , n - 1 \} \end{equation} Clearly: \begin{equation} \Sigma_{2} \; = \; \Sigma \end{equation} Considered a partition $ A \, = \, \{ A_{i} \}_{i = 1}^{n} \in \, {\mathcal{P}}(X , \mu) $ \begin{definition} \label{def:symbolic translator w.r.t. a partition} \end{definition} SYMBOLIC TRANSLATOR OF CDS W.R.T. A: $ \psi_{A} \, : \, X \rightarrow \Sigma_{n} $: \begin{equation} \psi_{A} ( x ) \; := \; j \, : \, x \in A_{j} \end{equation} In this way one associate to each point of X the letter, in the alphabet having as many letters as the number of atoms of the considered partition, labelling the atom to which the point belongs. Concatenating the letters corresponding to the phase-point at different times one can then codify $ k \in {\mathbb{N}}$ steps of the dynamics: \begin{definition} \label{def:n-point symbolic translator w.r.t. a partition} \end{definition} k-POINT SYMBOLIC TRANSLATOR OF CDS W.R.T. A: $ \psi_{A}^{(k)} \, : \, X \, \rightarrow \Sigma_{n}^{k} $: \begin{equation} \psi_{A}^{(k)} ( x ) \; := \; \cdot_{j = 1}^{n} \psi ( T^{j} x ) \end{equation} and whole orbits: \begin{definition} \label{def:orbit symbolic translator w.r.t. a partition} \end{definition} $ \psi_{A}^{(\infty)} \, : \, X \, \rightarrow \, \Sigma_{n}^{\infty} $: \begin{equation} \psi_{A}^{( \infty)} ( x ) \; := \; \cdot_{j = 1}^{\infty} \psi ( T^{j} x ) \end{equation} \medskip The bug of this strategy of symbolic translation is the dependence of the used alphabet from the cardinality of the partition: \begin{equation} card(A) \, \neq \, card(B) \; \Rightarrow \\ Range[ \psi_{A} ( x) ] \, \neq \, Range[ \psi_{B} ( x ) ] \; \; \forall x \in A \, , \, \forall A , B \in {\mathcal{P}}( \, X \, , \, \mu ) \end{equation} I will therefore adopt a different strategy of symbolic-coding using only the binary alphabet $ \Sigma $ first introduced in \cite{Segre-02}, based on the following: \begin{definition} \label{def:universal symbolic translator} \end{definition} UNIVERSAL SYMBOLIC TRANSLATOR OF CDS: $ \Psi \, : \, X \, \times \, {\mathcal{P}}( \, X \, , \, \mu ) \rightarrow {\Sigma^{\star} } $: \begin{equation} \Psi ( x \, , \, \{ A_{i} \}_{i = 1}^{n} ) \; := \; string( j) \; \; , \, x \, \in \, A_{j} \end{equation} that can be again used to codify $ k \in {\mathbb{N}}$ steps of the dynamics: \begin{definition} \label{def:k-point universal symbolic translator} \end{definition} k-POINT UNIVERSAL SYMBOLIC TRANSLATOR OF CDS: $ \Psi^{(k)} \, : \, X \, \times \, {\mathcal{P}}( \, X \, , \, \mu ) \rightarrow \Sigma^{\star} $: \begin{equation} \Psi^{(k)} ( x \, , \, \{ A_{i} \}_{i = 1}^{n} ) \; := \; \cdot_{j = 1}^{k} \psi ( T^{j} x \, , \, \{ A_{i} \}_{i = 1}^{n} ) \end{equation} and whole orbits: \begin{definition} \label{def:orbit universal symbolic translator} \end{definition} ORBIT UNIVERSAL SYMBOLIC TRANSLATOR OF CDS: $ \Psi^{(\infty)} \, : \, X \, \times \, {\mathcal{P}}( \, X \, , \, \mu ) \rightarrow \Sigma^{\infty} $: \begin{equation} \Psi^{(\infty)} ( x \, , \, \{ A_{i} \}_{i = 1}^{n} ) \; := \; \cdot_{j = 1}^{\infty} \psi ( T^{j} x \, , \, \{ A_{i} \}_{i = 1}^{n} ) \end{equation} The asymptotic rate of acquisition of \emph{plain Kolmogorov complexity} of the binary sequence obtained translating symbolically the orbit generated by $ x \in X $ through the partition $ A \, \in \, {\mathcal{P}} ( X \, , \, \mu ) $ is clearly given by: \begin{definition} \end{definition} \begin{equation} B( A \, , \, x) \; := \; B ( \Psi^{\infty}( x , A )) \end{equation} We saw in definition\ref{def:Kolmogorov-Sinai entropy} that the \emph{Kolmogorov-Sinai entropy} was defined as $ K( A \, , \, x) $ computed on the more probabilistically-informative A-experiment; in the same way the \emph{Brudno algorithmic entropy of x} is defined as the value of $ B( A \, , \, x) $ computed on the more algorithmically-informative A-experiment: \begin{definition} \label{def:Brudno algorithmic entropy of a point} \end{definition} BRUDNO ALGORITHMIC ENTROPY OF (THE ORBIT STARTING FROM) x: \begin{equation} B_{CDS} (x) \; := \; sup_{A \in {\mathcal{P}}(X , \mu)} B( \Psi^{(\infty)} ( x, A ) ) \end{equation} Demanding to \cite{Segre-02} for further details, let us recall that, as it is natural for different approaches of studying a same object, the \emph{probabilistic approach} and the \emph{algorithmic approach} to Classical Information Theory are deeply linked: the partial map $ D_{I} : \Sigma^{\star} \stackrel{ \circ } { \mapsto } \Sigma^{\star} $ defined by: \begin{equation} D_{I}( \vec{x} ) \; := \; \vec{x}^{\star} \end{equation} is by construction a prefix-code of pure algorithmic nature, so that it would be very reasonable to think that it may me optimal only for some ad hoc probability distribution, i.e. that for a generic probability distribution P the \emph{average code word length of $ D_{I} $ w.r.t. P}: \begin{equation} L_{ D_{I} , P } \; = \; \sum_{\vec{x} \in HALTING( D_{I} )} P( \vec{x}) I( \vec{x}) \end{equation} won't achieve the optimal bound, the Shannon information H(P), stated by the corner stone of Classical Probabilistic Information, i.e. the following celebrated: \begin{theorem} \label{th:classical noiseless coding theorem} \end{theorem} CLASSICAL NOISELESS CODING THEOREM \begin{equation} H(P) \; \leq \; L_{P} \; \leq \; H(P)+1 \end{equation} (where $ L_{P} $ is the \emph{minimal average code word length allowed by the distribution P}) Contrary, the deep link between the \emph{probabilistic-approach} and the \emph{algorithmic-approach} makes the miracle: under mild assumptions about the distribution P the code $ D_{I} $ is optimal as is stated by the following: \begin{theorem} \label{th:link between classical probabilistic information and classical algorithmic information} \end{theorem} LINK BETWEEN CLASSICAL PROBABILISTIC INFORMATION AND CLASSICAL ALGORITHMIC INFORMATION: \begin{hypothesis} \end{hypothesis} P recursive classical probability distribution over $ \Sigma^{\star} $ \begin{thesis} \end{thesis} \begin{equation} \exists c_{P} \in {\mathbb{R}}_{+} \; : \; 0 \, \leq \, L_{D_{I},P} - H(P) \, \leq \, c_{P} \end{equation} With an eye at theorem\ref{th:plain-prefix insensitivity of Brudno algorithmic entropy} it is then natural to expect that such a link between \emph{classical probabilistic information} and \emph{classical algorithmic information} generates a link between the asymptotic rate of acquisition of \emph{classical probabilistic information} and the asymptotic rate of acquisition of \emph{classical algorithmic information} of the coarse grained dynamics of CDS observed by repetions of the experiments for which each of them is maximal. Demanding to \cite{Segre-02} for further details such a reasoning, properly formalized, proves the following: \begin{theorem} \label{th:Brudno theorem} \end{theorem} BRUDNO'S THEOREM: HP: \begin{center} CDS ergodic \end{center} TH: \begin{equation} h_{CDS} \; = \; B_{CDS} (x) \; \; \forall - \mu - a.e. \, x \in X \end{equation} Let us now consider the \textbf{algorithmic approach to Classical Chaos Theory} strongly supported by Joseph Ford, whose objective is the characterization of the concept of chaoticity of a classical dynamical system as the algorithmic-randomness of its symbolically-translated trajectories. To require such a condition for all the trajectories would be too restrictive since it is reasonable to allow a chaotic dynamical system to have a numerable number of periodic orbits. Let us introduce then following two notions: \begin{definition} \label{def:strong algorithmic chaoticity} \end{definition} CDS IS STRONGLY ALGORITHMICALLY-CHAOTIC: \begin{equation} \forall-\mu-a.e. x \in X \, , \, \exists A \in {\mathcal{P}}(X , \mu) \, : \, \Psi^{(\infty)} ( x \, , \, A) \in CHAITIN-RANDOM( \Sigma^{\infty}) \end{equation} \begin{definition} \label{def:weak algorithmic chaoticity} \end{definition} CDS IS WEAK ALGORITHMICALLY-CHAOTIC: \begin{equation} \forall-\mu-a.e. x \in X \, , \, \exists A \in {\mathcal{P}}(X , \mu) \, : \, \Psi^{(\infty)} ( x \, , \, A) \in BRUDNO-RANDOM( \Sigma^{\infty}) \end{equation} The difference between definition\ref{def:strong algorithmic chaoticity} and definition\ref{def:weak algorithmic chaoticity} follows by Theorem\ref{th:Brudno randomness is weaker than Chaitin randomness}. Clearly Theorem\ref{th:Brudno theorem} implies the following: \begin{corollary} \label{cor:chaoticity versus algorithmic chaoticity} \end{corollary} \begin{align*} CHAOTICITY \; \; & = \; \; \text{WEAK ALGORITHMIC CHAOTICITY} \\ CHAOTICITY \; \; & < \; \; \text{STRONG ALGORITHMIC CHAOTICITY} \end{align*} that shows that the algorithmic approach to Classical Chaos Theory is equivalent to the usual one only in weak sense. The plethora of wrong statements in the mentioned \emph{new-age folklore on complexity} caused by the ignorance of corollary \ref{cor:chaoticity versus algorithmic chaoticity} is anyway of little importance if compared with the complete misunderstanding of the difference existing among the concepts of \emph{chaoticity} and \emph{complexity} for classical dynamical system; with this regards the analysis made in section\ref{sec:The shallowness of random objects} may be now thoroughly formalized introducing the following natural notions: \begin{definition} \label{def:strong-complexity for classical dynamical systems} \end{definition} CDS IS STRONGLY-COMPLEX: \begin{equation} \forall-\mu-a.e. x \in X \, , \, \exists A \in {\mathcal{P}}(X , \mu) \, : \, \Psi^{(\infty)} ( x \, , \, A) \in STRONGLY-COMPLEX( \Sigma^{\infty}) \end{equation} \begin{definition} \label{def:weak-complexity for classical dynamical systems} \end{definition} CDS IS WEAKLY-COMPLEX: \begin{equation} \forall-\mu-a.e. x \in X \, , \, \exists A \in {\mathcal{P}}(X , \mu) \, : \, \Psi^{(\infty)} ( x \, , \, A) \in WEAKLY-COMPLEX( \Sigma^{\infty}) \end{equation} One has that: \begin{theorem} \label{th:weak-shallowness of chaotical dynamical systems} \end{theorem} WEAK-SHALLOWNESS OF CHAOTIC DYNAMICAL SYSTEMS: \begin{center} CDS CHAOTIC $ \Rightarrow $ CDS WEAKLY-SHALLOW \end{center} \begin{proof} The thesis immediately follows combining theorem\ref{th:weak-shallowness of random sequences of cbits} with the definitions def.\ref{def:strong-complexity for classical dynamical systems} and def.\ref{def:weak-complexity for classical dynamical systems} \end{proof} \newpage \section{The physical complexity of strings and sequences of qubits} The idea that the physical complexity of a quantum object has to be measured in terms of a quantum analogue of Bennett's notion of \emph{logical depth} has been first proposed by Michael Nielsen \cite{Nielsen-02a},\cite{Nielsen-02b}. Unfotunately, beside giving some general remark about the properties he think such a notion should have, Nielsen have not given a mathematical definition of it. The first step in this direction consists, in my opinion, in considering that, such as the notion of \emph{classical-logical-depth} belongs to the framework of Classical Algorithmic Information Theory, the notion of \emph{quantum-logical-depth} belongs to the framework of Quantum Algorithmic Information Theory \cite{Segre-02}. One of the most debated issue in such a discipline, first discussed by it father Karl Svozil \cite{Svozil-96} and rediscovered later by the following literature \cite{Manin-99}, \cite{Vitanyi-99}, \cite{Berthiaume-van-Dam-Laplante-00}, \cite{Gacs-00}, \cite{Vitanyi-01}, \cite{Segre-02}, is whether the programs of the involved universal quantum computers have to be strings of cbits or strings of qubits. As I have already noted in \cite{Segre-02}, anyway, it must be observed that, owing to the natural bijection among $ {\mathcal{E}}_{\star} $ and $ \Sigma^{\star}$, one can always assume that the input is a string of qubits while the issue, more precisely restated, is whether the input has (or not) to be constrained to belong to the computational basis. So, denoted by $ {\mathcal{H}}_{2} := {\mathbb{C}}^{2} $ the one-qubit Hilbert space (endowed with its orthonormal computational basis $ {\mathcal{E}}_{2} := \{ | i > , i \in \Sigma \} $) , denoted by $ {\mathcal{H}}_{2}^{\bigotimes n } := \bigotimes_{k=0}^{n} {\mathcal{H}}_{2} $ the \emph{n-qubit Hilbert space}, (endowed with its orthonormal computational basis $ {\mathcal{E}}_{n} := \{ | \vec{x} > , \vec{x} \in \Sigma^{n} \} $), denoted by $ {\mathcal{H}}_{2}^{\bigotimes \star} := \bigoplus_{n=0}^{\infty} {\mathcal{H}}_{2}^{\bigotimes n}$ the \emph{Hilbert space of qubits' strings} (endowed with its orthonormal computational basis $ {\mathcal{E}}_{\star} := \{ | \vec{x} > , \vec{x} \in \Sigma^{\star} \} $) and denoted by $ {\mathcal{H}}_{2}^{\bigotimes \infty} $ the \emph{Hilbert space of qubits' sequences} (endowed with its orthonormal computational rigged-basis $ {\mathcal{E}}_{\infty} := \{ | \bar{x} > , \, \bar{x} \in \Sigma^{\infty} \} $), one simply assumes that, instead of being a \emph{classical Chaitin universal computer}, U is a \emph{quantum Chaitin universal computer}, i.e. a universal quantum computer whose input, following Svozil's original position on the mentioned issue, is constrained to belong to $ {\mathcal{E}}_{\star} $ and is such that, w.r.t. the natural bijection among $ {\mathcal{E}}_{\star} $ and $ \Sigma^{\star}$, satisfies the usual Chaitin constraint of having prefix-free halting-set. The definition of the logical depth of a string of cbits is then straightforward: given a vector $ | \psi > \in {\mathcal{H}}_{2}^{\bigotimes \star} $ and a string $ \vec{x} \in \Sigma^{\star} $: \begin{definition} \label{def:canonical program of a vector} \end{definition} CANONICAL PROGRAM OF $ | \psi > $: \begin{equation} | \psi >^{\star} \; := \; \min_{<_{l}} \min_{| \cdot | } \{ \vec{y} \in \Sigma^{\star} \, : \, U( \vec{y} ) = | \psi > \} \end{equation} \begin{definition} \end{definition} HALTING TIME OF THE COMPUTATION WITH INPUT $ | \vec{x} > $: \begin{equation} T( \vec{x} ) \; := \; \left\{% \begin{array}{ll} \text{number of computational steps after which U halts on input $ \vec{x} $ }, & \hbox{if $ U(\vec{x}) = \downarrow$} \\ + \infty, & \hbox{otherwise.} \\ \end{array}% \right. \end{equation} \begin{definition} \label{def:logical depth of a string of qubits} \end{definition} LOGICAL DEPTH OF $ | \psi > $ AT SIGNIFICANCE LEVEL s: \begin{equation} D_{s}( | \psi > ) \; := \; \min \{ T( \vec{y} ) \, : \, U( \vec{y} ) \, = \, | \psi > \, , \, \vec{y} \text{ s-incompressible } \} \end{equation} \begin{definition} \end{definition} $ | \psi > $ IS t-DEEP AT SIGNIFICANCE LEVEL s: \begin{equation} D_{s}( | \psi > ) \; > \; t \end{equation} \begin{definition} \end{definition} $ | \psi > $ IS t-SHALLOW AT SIGNIFICANCE LEVEL s: \begin{equation} D_{s}( | \psi > ) \; \leq \; t \end{equation} I will denote the set of all the t-deep strings of qubits as $ t-DEEP( {\mathcal{H}}_{2}^{\bigotimes \star} ) $. Let us observe that a sharp distinction among \emph{deepness} and \emph{shallowness} of qubits' strings is impossible; this is nothing but a further confirmation of the fact, so many times shown and analyzed in \cite{Segre-02}, that almost all the concepts of Algorithmic Information Theory, both Classical and Quantum, have a clear, conceptually sharp meaning only when sequences are taken into account. The great complication concerning sequences of qubits consists in that their mathematically-rigorous analysis requires to give up the simple language of Hilbert spaces passing to the more sophisticated language of \emph{noncommutative spaces}; indeed, as extensively analyzed in \cite{Segre-02} adopting the notion of \emph{noncommutative cardinality} therein introduced, the fact that the correct noncommutative space of qubits' sequences is the hyperfinite $ II_{1} $ factor: \begin{definition} \end{definition} NONCOMMUTATIVE SPACE OF QUBITS' SEQUENCES: \begin{equation} \Sigma_{NC}^{\infty} \; := \; \bigotimes _{n=0}^{\infty} ( M_{2} ({\mathbb{C}} ) \, , \, \tau_{unbiased} ) \; = \; R \end{equation} and not the noncommutative space $ {\mathcal{B}} ( {\mathcal{H}_{2}}^{\bigotimes \infty}) $ of all the bounded linear operators on $ {\mathcal{H}_{2}}^{\bigotimes \infty} $ (that could be still managed in the usual language of Hilbert spaces) is proved by the fact that, as it must be, $ \Sigma_{NC}^{\infty} $ has the \emph{continuum noncommutative-cardinality}: \begin{equation} card_{NC} ( \Sigma_{NC}^{\infty} ) \; = \; \aleph_{1} \end{equation} while $ {\mathcal{B}} ( {\mathcal{H}_{2}}^{\bigotimes \infty}) $ has only the \emph{countable noncommutative cardinality}. While the definition\ref{def:strongly-deep sequence of cbits} of a strongly-deep sequence of cbits has no natural quantum analogue, the definition of a weakly-deep sequence of qubits is straightforward. Denoted by $ RANDOM( \Sigma_{NC}^{\infty} ) $ the space of all the algorithmically random sequences of qubits, for whose characterization I demand to \cite{Segre-02}, let us observe that the equality between \emph{truth-table reducibility} and \emph{recursive time bound reducibility} existing as to Classical Computation may be naturally imposed to Quantum Computation in the following way: given two arbitary mathematical quantities x and y: \begin{definition} \end{definition} x IS QUANTUM-TRUTH-TABLE REDUCIBLE TO y: \begin{equation} x \, \leq_{tt}^{Q} \, y \; := \; \text{x is U-computable from y in bounded U-computable time} \end{equation} Given a sequence of qubits $ \bar{a} \in \Sigma_{NC}^{\infty} $: \begin{definition} \label{def:weakly-deep sequence of qubits} \end{definition} $ \bar{a} $ IS WEAKLY-DEEP: \begin{equation} \exists \bar{b} \in RANDOM (\Sigma_{NC}^{\infty} ) \, : \, \bar{a} \; >_{tt}^{Q} \; \bar{b} \end{equation} Denoted the set of all the weakly-deep sequences of qubits as $ WEAKLY-DEEP(\Sigma_{NC}^{\infty} ) $: \begin{definition} \end{definition} WEAKLY-SHALLOW SEQUENCES OF QUBITS: \begin{equation} WEAKLY-SHALLOW(\Sigma_{NC}^{\infty} ) \; := \; \Sigma_{NC}^{\infty} \, - \, WEAKLY-DEEP(\Sigma_{NC}^{\infty} ) \end{equation} It is natural, at this point, to conjecture that an analogue of theorem\ref{th:alternative characterization of weakly-shallow sequences of cbits} exist in Quantum Algorithmic Information Theory too: \begin{conjecture} \label{con:alternative characterization of weakly-shallow sequences of qubits} \end{conjecture} ALTERNATIVE CHARACTERIZATION OF WEAKLY-SHALLOW SEQUENCES OF QUBITS: \begin{equation} \bar{a} \in WEAKLY-SHALLOW(\Sigma_{NC}^{\infty} )) \; \Leftrightarrow \; \exists \omega \in S(\Sigma_{NC}^{\infty}) \, U-computable \; : \; \bar{a} \in \omega-RANDOM( \Sigma_{NC}^{ \infty }) \end{equation} where $ \omega-RANDOM( \Sigma_{NC}^{ \infty} ) $ denotes the set of all the $ \omega$- random sequences of qubits w.r.t. the state $ \omega \in S(\Sigma_{NC}^{\infty}) $ to be defined generalizing the definition of $ RANDOM( \Sigma_{NC}^{ \infty} ) $ to states different by $ \tau_{unbiased} $ along the lines indicated in \cite{Segre-02} as to the definition of the \emph{laws of randomness} $ {\mathcal{L}}^{NC}_{RANDOMNESS} ( \Sigma_{NC}^{ \infty} \, , \, \omega ) $ of the \emph{noncommutative probability space} $ ( \Sigma_{NC}^{ \infty} \, , \, \omega ) $. As to sequences of qubits, the considerations made in the section\ref{sec:The shallowness of random objects} may be thoroughly formalized, at the prize of assuming the conjecture\ref{con:alternative characterization of weakly-shallow sequences of qubits} as an hypothesis, through the following: \begin{theorem} \label{th:weak-shallowness of random sequences of qubits} \end{theorem} WEAK-SHALLOWNESS OF RANDOM SEQUENCES OF QUBITS: HP: \begin{center} Conjecture\ref{con:alternative characterization of weakly-shallow sequences of qubits} holds \end{center} TH: \begin{equation} RANDOM( \Sigma_{NC}^{ \infty} ) \, \cap \, WEAKLY-DEEP(\Sigma_{NC}^{\infty}) \; = \; \emptyset \end{equation} \begin{proof} Since the \emph{unbiased state} $ \tau_{unbiased} $ is certainly U-computable and by definition: \begin{equation} RANDOM( \Sigma_{NC}^{ \infty} ) \; = \; \tau_{unbiased} - RANDOM( \Sigma_{NC}^{ \infty} ) \end{equation} assuming the conjecture\ref{con:alternative characterization of weakly-shallow sequences of qubits} as an hypothesis, it immediately lead to the thesis \end{proof} \newpage \section{The physical complexity of quantum dynamical systems} As we have seen in section\ref{sec:The physical complexity of classical dynamical systems} the Kolmogorov-Sinai entropy $ h_{KS} (CDS ) $ of a \emph{classical dynamical system} $ CDS \, := \, ( X \, , \, \mu \, , \, T ) $ have a clear physical information-theoretic meaning that we can express in the following way: \begin{enumerate} \item an experimentalist is trying to obtain information about the dynamical evolution of CDS performing repeatedly on the system a given experiment $ exp \in EXPERIMENTS $, \item $ h(exp \, , \, CDS) $ is the asymptotic rate of acquisition of classical information about the dynamics of CDS that he acquires replicating exp \item $ h_{KS} (CDS ) $ is such an asymptotic rate, computed for the more informative possible experiment: \begin{equation} \label{eq:physical meaning of the Kolmogorov Sinai entropy} h_{KS} (CDS ) \; = \; \sup_{exp \in EXPERIMENTS} h(exp \, , \, CDS) \end{equation} \end{enumerate} Let us now pass to analyze quantum dynamical systems, for whose definition and properties I demand to \cite{Segre-02}. Given a \emph{quantum dynamical system} QDS the physical information-theoretical way of proceeding would consist in analyzing the same experimental situation in which an experimentalist is trying to obtain information about the dynamical evolution of QDS performing repeatedly on the system a given experiment $ exp \in EXPERIMENTS $: \begin{enumerate} \item to define $ h(exp \, , \, QDS) $ as the asymptotic rate of acquisition of information about the dynamics of CDS that he acquires replicating the experiment exp \item to define the \emph{dynamical entropy} of QDS as such an asymptotic rate, computed for the more informative possible experiment: \end{enumerate} resulting in the following: \begin{definition} \label{def:dynamical entropy of a quantum dynamical system} \end{definition} DYNAMICAL ENTROPY OF QDS \begin{equation} h_{d.e.} (QDS) \; = \; \sup_{exp \in EXPERIMENTS} h(exp \, , \, QDS) \end{equation} \begin{definition} \label{def:quantum chaoticity} \end{definition} QDS IS CHAOTIC: \begin{equation} h_{d.e.} (QDS) \; > \; 0 \end{equation} The irreducibility of Quantum Information Theory to Classical Information Theory, caused by the fact that theorem\ref{th:the soul of Classical Information Theory} doesn't extend to the quantum case owing to the existence of some non-accessible information about a quantum system (as implied by the Gr\"{o}nwald-Lindblad-Holevo Theorem) and the consequent irreducibility of the qubit to the cbit \cite{Nielsen-Chuang-00}, \cite{Segre-02} would then naturally lead to the physical issue whether the information acquired by the experimentalist is classical or quantum, i.e. if $ h_{d.e.} (QDS) $ is a number of cbits or a number of qubits. Such a physical approach to quantum dynamical entropy was performed first by G\"{o}ran Lindblad \cite{Lindblad-79} and later refined and extended by Robert Alicki and Mark Fannes resulting in the so called \emph{Alicki-Lindblad-Fannes entropy} \cite{Alicki-Fannes-01}. Many attempts to define a quantum analogue of the \emph{Kolmogorov-Sinai entropy} pursued, instead, a different purely mathematical approach consisting in generalizing noncommutatively the mathematical machinery of partitions and coarsest-refinements underlying the definition\ref{def:Kolmogorov-Sinai entropy} obtaining mathematical objects, whose (eventual) physical meaning was investigated subsequently. This was certainly the case as to the \emph{Connes-Narnhofer-Thirring entropy} , the \emph{entropy of Sauvageot and Thouvenot} and \emph{Voiculescu's approximation entropy} \cite{Connes-Narnhofer-Thirring-87}, \cite{Stormer-02}. As to the \emph{Connes-Narnhofer-Thirring entropy}, in particular, the noncommutative analogue playing the role of the classical partitions are the so called \emph{Abelian models} whose (eventual) physical meaning is rather obscure since, as it has been lucidly shown by Fabio Benatti in his very beautiful book \cite{Benatti-93}, don't correspond to physical experiments performed on the system, since even a projective-measurement (i.e. a measurement corresponding to a Projection Valued Measure) cannot, in general, provide an abelian model, since its reduction-formula corresponds to a decomposition of the state of the system if and only if the measured observable belongs to the centralizer of the state of the system. It may be worth observing, by the way, that the non-existence of an agreement into the scientific community as to the correct quantum analogue of the \emph{Kolmogorov-Sinai entropy} and hence on the definition of \emph{quantum chaoticity} shouldn't surprise, such an agreement lacking even for the well more basic notion of \emph{quantum ergodicity}, \emph{Zelditch's quantum ergodicity} \cite{Zelditch-96}, more in the spirit of the original \emph{Von Neumann's quantum ergodicity} \cite{von-Neumann-29} to which it is not anyway clear if reduces exactly as to quantum dynamical systems of the form $( A \, , \, \omega \, , \, \alpha )$ with $ card_{NC} (A) \leq \aleph_{0} $ and $ \alpha \in INN(A) $, differing from \emph{Thirring's quantum ergodicity} \cite{Thirring-83} adopted both in \cite{Benatti-93} and in \cite{Alicki-Fannes-01}. Returning, now, to the physical approach based on the definition\ref{def:dynamical entropy of a quantum dynamical system}, the mentioned issue whether the dynamical entropy $ h_{d.e.} (QDS) $ is a measure of \emph{classical information} or of \emph{quantum information} (i.e. if it is a number of cbits or qubits) is of particular importance as soon as one tries to extend to the quantum domain Joseph Ford's algorithmic approach to Chaos Theory seen in section\ref{sec:The physical complexity of classical dynamical systems}: \begin{enumerate} \item in the former case, in fact, one should define \emph{quantum algorithmic chaoticity} by the requirement that almost all the trajectories, simbolically codified in a suitable way, belong to $ BRUDNO ( \Sigma^{\infty} )$ for \emph{quantum weak algorithmic chaoticity} and to $ CHAITIN-RANDOM( \Sigma^{\infty} ) $ for \emph{quantum strong algorithmic chaoticity} \item in the latter case, instead, one should define \emph{quantum algorithmic chaoticity} by the requirement that almost all the trajectories, simbolically codified in a suitable way, belong to $ RANDOM ( \Sigma_{NC}^{\infty} ) $ \end{enumerate} In any case one would then be tempted to conjecture the existence of a Quantum Brudno's Theorem stating the equivalence of \emph{quantum chaoticity} and \emph{quantum algorithmic chaoticity}, at least in weak sense, for \emph{quantum ergodic dynamical systems}. The mentioned issue whether the dynamical entropy $ h_{d.e.} (QDS) $ is a measure of \emph{classical information} or of \emph{quantum information} (i.e. if it is a number of cbits or qubits) is of great importance also as to the definition of a \emph{deep quantum dynamical system} (i.e. a \emph{physically-complex quantum dynamical system}): \begin{enumerate} \item in the former case, in fact, one should define a \emph{strong (weak) - deep quantum dynamical system} as a quantum dynamical system such that almost all its trajectories, simbolically codified in a suitable way, belong to $ STRONG-DEEP( \Sigma^{\infty}) ( WEAK-DEEP( \Sigma^{\infty} ))$. \item in the latter case, instead, one should define a \emph{weak-deep quantum dynamical system} as a quantum dynamical system such that almost all its trajectories, simbolically codified in a suitable way, belong to $ WEAK-DEEP( \Sigma_{NC}^{\infty} ) $ \end{enumerate} In any case, or by the theorem\ref{th:weak-shallowness of random sequences of cbits} or by the theorem\ref{th:weak-shallowness of random sequences of qubits}, one would be almost certainly led to a quantum analogue of theorem\ref{th:weak-shallowness of chaotical dynamical systems} stating that a \emph{chaotic quantum dynamical system} is \emph{weak-shallow}, i.e. is not \emph{physically complex}. \newpage \begin{thebibliography}{10} \bibitem{Adleman-79} L.~Adleman. \newblock {T}ime, {S}pace and {R}andomness. \newblock Technical Report LCS/TM-131, MIT, April 1979. \bibitem{Boffetta-Cencini-Falcioni-Vulpiani-01} G.~Boffetta M. Cencini M.~Falcioni A.Vulpiani. \newblock Predictability: a way to characterize {C}omplexity. \newblock {\em Physics Reports}, 356:367--474, 2001. \newblock nlin.CD/0101029 \bibitem{Benatti-93} F.~Benatti. \newblock {\em Deterministic Chaos in Infinite Quantum Systems}. \newblock Springer Verlag, Berlin, 1993. \bibitem{Bennett-82} C.H. Bennett. \newblock On the logical depth of sequences and their reducivilities to random sequences. \newblock unpublished manuscript, 1982. \bibitem{Bennett-85} C.H. Bennett. \newblock Information, dissipation, and the definition of organization. \newblock In D.~Pines, editor, {\em {E}merging {S}intheses in {S}cience}. Santa Fe Institute, Santa Fe (New Mexico), 1985. \bibitem{Bennett-88} C.H. Bennett. \newblock Logical depth and physical complexity. \newblock In R.H. Herken, editor, {\em The Universal Turing machine; A Half-Century Survey}, pages 227--258. Oxford University Press, Oxford, 1988. \newblock also available at Tom Toffoli's {Q}uantum {C}omputation {A}rchive at http://pks.bu.edu/qcl/. \bibitem{Billingsley-65} P.~Billingsley. \newblock {\em Ergodic Theory and Information}. \newblock John Wiley and Sons Inc., 1965. \bibitem{Brudno-78} A.A. Brudno. \newblock The complexity of the trajectories of a dynamical system. \newblock {\em Russian Mathematical Surveys}, 33(1):197--198, 1978. \bibitem{Brudno-83} A.A. Brudno. \newblock Entropy and the complexity of the trajectories of a dynamical system. \newblock {\em Trans. Moscow Math. Soc.}, 44:127, 1983. \bibitem{Calude-02} C.~Calude. \newblock {\em Information and Randomness. An Algorithmic Perspective}. \newblock Springer Verlag, Berlin, 2002. \bibitem{Chaitin-77} G.~Chaitin. \newblock Algorithmic information theory. \newblock {\em IBM J. Res.}, (21):350--359, 1977. \bibitem{Nielsen-Chuang-00} M.A. Nielsen~I.L. Chuang. \newblock {\em Quantum Computation and Quantum Information}. \newblock Cambridge University Press, Cambridge, 2000. \bibitem{Alicki-Fannes-01} R.~Alicki~M. Fannes. \newblock {\em Quantum dynamical systems}. \newblock Oxford University Press, Oxford, 2001. \bibitem{Gacs-86} P.~Gacs. \newblock Every sequence is reducible to a random sequence. \newblock {\em Inf. Contr.}, 70:186--192, 1986. \bibitem{Gacs-00} P.~Gacs. \newblock Quantum {A}lgorithmic {E}ntropy. \newblock {\em J. Phys. A: Math. Gen.}, 34:1--22, 2000. \newblock quant-ph/0001046. \bibitem{Hartmanis-83} J.~Hartmanis. \newblock {G}eneralized {K}olmogorov complexity and the structure of the feasible computation. \newblock In {\em Proceedings of the $ 24^{th}$ IEEE {S}ymposium on the {F}oundations of {C}omputer {S}cience}, pages 439--445. 1983. \bibitem{Kolmogorov-83b} A.N. Kolmogorov. \newblock On the logical foundations of probability theory. \newblock In A.N. Shiryayev, editor, {\em Selected {W}orks of A.N. {K}olmogorov - {V}olume2: {P}robability {T}heory and {M}athematical {S}tatistics}, pages 515--519. Kluwer Academic Publishers, Dordrecht, 1992. \newblock originally appeared as {L}ecture {N}otes in {M}athematics, 1983, 1021, pp. 1-5. \bibitem{Kolmogorov-83a} A.N. Kolmogorov. \newblock The combinatorial foundations of information theory and the probability calculus. \newblock In A.N. Shiryayev, editor, {\em Selected {W}orks of A.N. {K}olmogorov - {V}olume3: {I}nformation {T}heory and the {T}heory of {A}lgorithms}, pages 208--218. Kluwer Academic Publishers, Dordrecht, 1993. \newblock originally appeared in {U}spekhi {M}at. {N}auk, 1983, vol.38, vyp.4, pp. 27-36. \bibitem{Kolmogorov-58} A.N. Kolmogorov. \newblock New metric invariant of transitive dynamical systems and automorphims of lebesgue space. \newblock In A.N. Shiryayev, editor, {\em Selected {W}orks of A.N. {K}olmogorov - {V}olume3: {I}nformation {T}heory and the {T}heory of {A}lgorithms}, pages 57--61. Kluwer Academic Publishers, Dordrecht, 1993. \newblock originally appeared in {D}okl. {A}kaud. {N}auk SSSR, 1958, vol. 119, n. 5, pp. 861-864. \bibitem{Kolmogorov-65} A.N. Kolmogorov. \newblock Three approaches to the definition of the notion of amount of information. \newblock In A.N. Shiryayev, editor, {\em Selected {W}orks of A.N. {K}olmogorov - {V}olume3: {I}nformation {T}heory and the {T}heory of {A}lgorithms}, pages 184--193. Kluwer Academic Publishers, Dordrecht, 1993. \newblock originally appeared in {P}roblemy {P}ederachi {I}nformatsii, vol.1, n.1, pp. 1-13, 1965. \bibitem{Kolmogorov-69} A.N. Kolmogorov. \newblock To the logical foundations of the theory of information and probability theory. \newblock In A.N. Shiryayev, editor, {\em Selected {W}orks of A.N. {K}olmogorov - {V}olume3: {I}nformation {T}heory and the {T}heory of {A}lgorithms}, pages 203--207. Kluwer Academic Publishers, Dordrecht, 1993. \newblock originally appeared in {P}roblemy {P}ederachi {I}nformatsii, 1969, vol.5, n.3, pp. 3-7. \bibitem{Levin-84} L.A. Levin. \newblock Randomness conservation inequalities: {I}nformation and independence in mathematical theories. \newblock {\em Inf. Contr.}, 61:15--37, 1984. \bibitem{Lindblad-79} G.~Lindblad. \newblock {N}on-markovian {Q}uantum {S}tochastic {P}rocesses and {T}heir {E}ntropies. \newblock {\em Commun. in Math. Phys.}, 65:281--294, 1979. \bibitem{Manin-99} Yu.I. Manin. \newblock Classical {C}omputing, {Q}uantum {C}omputing and {S}hor's {F}actoring {A}lgorithm. \newblock {\em quant-ph/9903008}. \newblock talk given at the Bourbaki Seminar , 12-13 June 1999 at the Institute Henri Poincar\'{e}, Paris. \bibitem{Nielsen-02b} M.~Nielsen. \newblock Quantum information science and complex quantum systems. \newblock {\em quant-ph/0210005}, 2002. \bibitem{Nielsen-02a} M.~Nielsen. \newblock Quantum information science as an approach to complex quantum systems. \newblock {\em quanth-ph/0208078}, 2002. \bibitem{Odifreddi-89} P.~Odifreddi. \newblock {\em Classical Recursion Theory: vol. 1}. \newblock Elsevier Science, Amsterdam, 1989. \bibitem{Odifreddi-99a} P.~Odifreddi. \newblock {\em Classical Recursion Theory: vol. 2}. \newblock Elsevier Science, Amsterdam, 1999. \bibitem{Segre-02} G.~Segre. \newblock {\em Algorithmic Information Theoretic Issues in Quantum Mechanics}. \newblock PhD thesis, Dipartimento di Fisica Nucleare e Teorica. quant-ph/0110018; mp-arc-01-390, Pavia (Italy), 2002. \newblock some errata corrige emended in the version at http://www.gavrielsegre.com \bibitem{Kornfeld-Sinai-00} I.P. Kornfeld~Y.G. Sinai. \newblock General {E}rgodic {T}heory of {G}roups of {M}easure {P}reseving {T}rasformations. \newblock In Y.G. Sinai, editor, {\em Dynamical Systems, Ergodic Theory abd Applications}. Springer Verlag, Berlin, 2000. \bibitem{Sinai-94} Ya.~G. Sinai. \newblock {\em Topics in Ergodic Theory}. \newblock Princeton University Press, Princeton, 1994. \bibitem{Sinai-76} Y.G. Sinai. \newblock {\em Introduction to Ergodic Theory}. \newblock Princeton University Press, Princeton, 1976. \bibitem{AMS-LMS-00} Am. Math. Society London~Math. Society. \newblock {\em Kolmogorov in Perspective}. \newblock American Mathematical Society, 2000. \bibitem{Staiger-99} L.~Staiger. \newblock The {K}olmogorov {C}omplexity of {R}eal {N}umbers. \newblock In G.~Ciobanu~Gh. Paun, editor, {\em Fundamentals of Computation Theory}, pages 536--546. Springer Verlag, Berlin, 1999. \newblock available at author's home-page: http://www.informatik.uni-halle.de/~staiger/. \bibitem{Stormer-02} E.~Stormer. \newblock A {S}urvey of {N}oncommutative {D}ynamical {E}ntropy. \newblock In M.~Rordam~E. Stormer, editor, {\em Classification of {N}uclear $ C^{\star}$-{A}lgebras. {E}ntropy in {O}perator {A}lgebras}, pages 148--198. Springer-Verlag, Berlin, 2002. \bibitem{Svozil-96} K.~Svozil. \newblock Quantum {A}lgorithmic {I}nformation {T}heory. \newblock {\em Journal of Universal Computer Science}, 2:311--346, 1996. \newblock quant-ph/9510005 \bibitem{Connes-Narnhofer-Thirring-87} A.~Connes H. Narnhofer~W. Thirring. \newblock {D}ynamical {E}ntropy of $ c^{\star} $ {A}lgebras and von {N}eumann {A}lgebras. \newblock In {\em {S}elected papers of {W}alter {E}. {T}hirring with commentaries}, pages 159--188. American Mathematical Society, Providence, Rhode Island, 1998. \newblock originally appeared in {C}ommun. {M}ath. {P}hys., 112, 691-719, (1987). \bibitem{Thirring-83} W.~Thirring. \newblock {\em A Course in Mathematical Physics - vol.4: Quantum Mechanics of Large Systems}. \newblock Springer-Verlag, Berlin, 1983. \bibitem{Berthiaume-van-Dam-Laplante-00} A.~Berthiaume~W. van Dam S.~Laplante. \newblock Quantum {K}olmogorov {C}omplexity. \newblock {\em quant-ph/0005018}, May 2000. \newblock To appear in the Proceedings of the 15th IEEE Annual Conference on Computational Complexity. \bibitem{Li-Vitanyi-97} M.~Li~P. Vitanyi. \newblock {\em An Introduction to Kolmogorov Complexity and Its Applications}. \newblock Springer Verlag, New York, 1997. \bibitem{Vitanyi-99} P.~Vitanyi. \newblock Two approaches to the {Q}uantitative {D}efinition of {I}nformation in an {I}ndividual {P}ure {Q}uantum {S}tate. \newblock {\em quant-ph/9907035}, July 1999. \bibitem{Vitanyi-01} P.M.B. Vitanyi. \newblock Quantum {K}olmogorov {C}omplexity based on {C}lassical {D}escriptions. \newblock {\em IEEE Transactions on Information Theory}, 47(6):2464--2479, 2001. \newblock quant-ph/0102108. \bibitem{Levin-Vjugin-77} L.A. Levin~V.V. V'Jugin. \newblock {I}nvariant {P}roperties of {I}nformational {B}ulks. \newblock pages 359--364. Springer-Verlag, 1977. \bibitem{von-Neumann-29} J.~von Neumann. \newblock Beweis des ergodensatzes und des {H}-theorems in der neuen mechanik. \newblock {\em Zschr. f. Physik}, 57:30--70, 1929. \bibitem{Wolfram-85} S.~Wolfram. \newblock {U}ndecidability and {I}ntractability in {T}heoretical {P}hysics. \newblock {\em Physical Review Letters}, 54:735--738, 1985. \bibitem{Alekseev-Yakobson-1981} V.M. Alekseev~M.V. Yakobson. \newblock Symbolic dynamics and hyperbolic dynamic systems. \newblock {\em Physics Reports}, 75(5):287--325, 1981. \bibitem{Zelditch-96} S.~Zelditch. \newblock Quantum ergodicity of {C}$^{\star} $ dynamical systems. \newblock {\em Comm. Math. Phys.}, 177:507--528, 1996. \end{thebibliography} \end{document} ---------------0210220710501--