Content-Type: multipart/mixed; boundary="-------------0110200752528" This is a multi-part message in MIME format. ---------------0110200752528 Content-Type: text/plain; name="01-390.comments" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="01-390.comments" 393 pages (including the Mathematica notebook of appendixA not reported here): my PHD-thesis ---------------0110200752528 Content-Type: text/plain; name="01-390.keywords" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="01-390.keywords" information, entropy ---------------0110200752528 Content-Type: application/x-tex; name="tesi.tex" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="tesi.tex" \documentclass{report} \title{Algorithmic Information Theoretic Issues in Quantum Mechanics} \author{Gavriel Segre - PHD thesis} \usepackage{amsmath,amssymb,graphicx} \numberwithin{equation}{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} \maketitle \tableofcontents \part{Preliminaries} \section{Warning} The project of this work, going beyond the possibility of realization (at least mine) during doctoral studies, has not been completed and has to be considered as \textbf{open}. To underline the intellectual path I tried to pursue, I have conserved the title and mentioning to the unrealized sections instead of eliminating them, thinking that they add anyway some cbit of classical information. \section{Acknowledgments} First of all I would like to thank my PHD-tutor, prof. Rimini, for having believed I was worth to be allowed to follow my own way and for many encouragements and skills. \smallskip Then I would like to thank doct. Benatti for having read, analyzed and often constructively criticized many parts of this work, and for having taught me so many things that it is difficult to me to mention all of them. In particular I am grateful to him for clarifying me the key point why some diagonalization-proofs don't generalize noncommutatively. \smallskip I then want strongly to thank prof. Jona-Lasinio for many invaluable remarks and teachings and, in particular, for having suggested me the idea of considering sequences of free coin tosses in view of Voiculescu's Central Limit Theorem. \smallskip Then I want to thank prof. Rasetti who introduced me to Word Problems, as well as to the Turing Barrier Problem of Quantum Mechanics and all the related issues. \smallskip I am very grateful to prof. Van Lambalgen for having given me a copy of his wonderful dissertation. \smallskip Then I would like to thank doct. Winter for having suggested me to partecipate to the Second Bielefeld Workshop on Quantum Information and Computation, giving me the motivations to pursue walking on my way. \smallskip Last but not least, I would like to thank prof. Odifreddi for many useful suggestions. \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 \\ $ 2^{S} $ & power-set of the set S \\ $ S^{0} $ & interior of the topological space S \\ $ \bar{S} $ & closure of the topological space S \\ $ {\mathcal{D}} ( A_{1} \, , \, A_{2} ) $ & description methods of $ A_{2} $ through $ A_{1} $ \\ $ {\mathcal{R}} $ & universe of description \\ $ \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 \\ $ \lambda $ & empty string \\ $ | \vec{x} | $ & length of the string $ \vec{x} $ \\ $ string(n) $ & $ n^{th} $ string in quasilexicographic order \\ $ |n | $ & length of the $ n^{th} $ string in quasilexicographic order \\ $ \bar{x} $ & sequence \\ $ <_{p} $ & prefix order relation \\ $ \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}(n,m) $ & substring of the sequence $ \bar{x} $ obtained taking the digits from the $n^{th}$ to the $m^{th}$ \\ $ \vec{x}^{n} $ & string made of n repetitions of the string $ \vec{x} $ \\ $ \vec{x} ^{\infty} $ & sequence made of infinite repetitions of the string $ \vec{x} $ \\ $ S \, \Sigma^{ \infty } $ & sequences having the strings of S as prefixes \\ $ \vec{x} \Sigma^{\infty} $ & sequences having the string $ \vec{x} $ as prefix \\ $ N_{i}( \vec{y}) $ & number of occurence of the letter i in the string $ \vec{y} $ \\ $ N_{i}^{n} ( \bar{x} ) $ & number of successive letters i ending in position n of the sequence $ \bar{x} $ \\ $ {\mathcal{I}} ( a , n , \vec{b} ) $ & string obtained inserting the letter a at the $ n^{th} $ place of the string $ \vec{b} $ \\ $ L_{D,P} $ & average code-word length w.r.t. the code D and the distribution P \\ $ H(P) $ & Shannon's entropy of the distribution P \\ $ K( \vec{x} ) $ & simple algorithmic entropy of the string $ \vec{x} $ \\ $ I( \vec{x} ) $ & prefix algorithmic entropy of the string $ \vec{x} $ \\ $ \Sigma(n) $ & busy-beaver function \\ $ P_{U} ( \vec{x} ) $ & universal probability of the string $ \vec{x}$ w.r.t. the universal Chaitin computer U \\ $ \Omega_{U} $ & halting probability of the universal Chaitin computer U \\ \hline \end{tabular} \newpage \begin{tabular}{|c|c|} $ CHAITIN-m-RANDOM ( \Sigma^{\star}) $ & Chaitin-m-random strings \\ $ CHAITIN-RANDOM ( \Sigma^{\star}) $ & Chaitin-random strings \\ $ {\mathcal{N}} ( \bar{x} ) $ & numeric representation of the sequence $ \bar{x} $ \\ $ CHAITIN-RANDOM(\Sigma^{\infty} )$ & Martin L\"{o}f- Solovay -Chaitin-random sequences \\ $ BRUDNO-RANDOM(\Sigma^{\infty} )$ & Brudno-random sequences \\ $ q-PSEUDORANDOM ( \Sigma^{\star} , V ) $ & pseudorandom strings of level q w.r.t. V \\ $ MARTINL\ddot{O}F-q-RANDOM( \Sigma^{\star} ) $ & Martin L\"{o}f pseudorandom strings of level q \\ $ \mu-RANDOM( \Sigma^{\infty} \, , \, \delta ) $ & Martin L\"{o}f $\mu$-random sequences w.r.t. $ \delta $ \\ $ \mu-RANDOM( \Sigma^{\infty}) $ & Martin L\"{o}f $\mu$-random sequences \\ $ {\mathcal{P}} (M) $ & unary predicates over the set M \\ $ {\mathcal{P}}_{TYPICAL} (CPS) $ & typical properties of CPS \\ $ {\mathcal{L}}_{RANDOMNESS} (CPS) $ & laws of randomness of CPS \\ $ P-CONF-RANDOM( \Sigma^{\infty} ) $ & conformistically-random sequences w.r.t. P \\ $ CONF-RANDOM( \Sigma^{\infty} ) $ & conformistically-random sequences \\ $ EXT[S] $ & subsequence extraction function w.r.t. S \\ $ CHURCH-RANDOM(\Sigma^{\infty} )$ & Church-random sequences \\ $ A \, \bigvee \, B $ & coarsest refinement of the partitions A and B \\ $ h_{CDS} $ & Kolmogorov-Sinai entropy of CDS \\ $ {\mathbb{N}} $ & natural numbers \\ $ {\mathbb{Z}} $ & integers numbers \\ $ {\mathbb{A}}_{n} $ & algebraic numbers of order n \\ $ {\mathbb{A}} $ & algebraic numbers \\ $ {\mathbb{Q}} $ & rational numbers \\ $ {\mathbb{R}} $ & real numbers \\ $ {\mathbb{C}} $ & complex numbers \\ $ {\mathbb{C}}P^{n} $ & complex projective space of order n \\ $ G_{k,n} ({\mathbb{C}}) $ & complex Grassmann manifold of order (k,n) \\ $ \aleph_{n} $ & $ (n+1)^{th} $ infinite cardinal \\ $ \Re(z) $ & real part of the complex number z \\ $ \Im(z) $ & imaginary part of the complex number z \\ $ f_{1} \, \stackrel{ + }{\leq} \, f_{2} $ & $ f_{1} $ is additively less or equal to $ f_{2} $ \\ $ f_{1} \, \stackrel{ + }{=} \, f_{2} $ & $ f_{1} $ is additively equal to $ f_{2} $ \\ $ f_{1} \, \stackrel{ \times }{\leq} \, f_{2} $ & $ f_{1} $ is multiplicatively less or equal to $ f_{2} $ \\ $ f_{1} \, \stackrel { \times }{=} \, f_{2} $ & $ f_{1} $ is multiplicatively equal to $ f_{2} $ \\ $ a \, | \, b $ & a divides b \\ $ a \, \nmid \, b $ & a does not divide b \\ gcd(a,b) & greatest common divisor of (a,b) \\ lcm(a,b) & least common multiple of (a,b) \\ $ \lfloor x \rfloor $ & floor of x: the greater integer less than or equal to x \\ $ \lceil x \rceil $ & ceiling of x: the least integer greater than or equal to x \\ $ x \; mod \, n $ & remainder: $ x - n \lfloor \frac{x}{n} \rfloor $ \\ $ MAP(A,B) $ & maps from A to B \\ $ f : A \mapsto B $ & map from A to B \\ $ \stackrel{ \circ } {MAP}(A,B) $ & partial maps from A to B \\ \hline \end{tabular} \newpage \begin{tabular}{|c|c|} % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... $ f : A \stackrel{ \circ } { \mapsto } B $ & partial map from A to B \\ $ C_{M} \, ( NC_{M} ) $ & mathematically-classical (mathematically-nonclassical) \\ $ C_{\Phi} \, ( NC_{\Phi} ) $ & physically-classical (physically-nonclassical) \\ $ REC $ & recursive \\ $ \Delta_{0}^{0} $ & computable \\ $ \varphi_{e}^{(n)} $ & n-ary partial recursive function with G\"{o}del number e \\ $ {\mathcal{W}}_{e}^{(n)} $ & halting set of $ \varphi_{e}^{(n)} $ \\ $ {\mathcal{L}}({\mathcal{H}}) $ & lattice of all the closed linear subspaces of the Hilbert space $ {\mathcal{H}} $ \\ $ {\mathcal{O}} ({\mathcal{H}} ) $ & linear operators on the Hilbert space $ {\mathcal{H}} $ \\ $ {\mathcal{B}}({\mathcal{H}}) $ & bounded linear operators on the Hilbert space $ {\mathcal{H}} $ \\ $ \| \cdot \|_{n} $ & $ n^{th} $ operatorial norm on $ {\mathcal{B}}({\mathcal{H}}) $ \\ $ | a | $ & modulus of the bounded operator a \\ $ {\mathcal{C}}_{n} ({\mathcal{H}}) $ & n-class bounded operators on the Hilbert space $ {\mathcal{H}} $ \\ $ {\mathcal{C}}_{1} ({\mathcal{H}}) $ & trace-class bounded operators on the Hilbert space $ {\mathcal{H}} $ \\ $ {\mathcal{C}}_{2} ({\mathcal{H}}) $ & Hilbert-Schmidt bounded operators on the Hilbert space $ {\mathcal{H}} $ \\ $ {\mathcal{C}} ({\mathcal{H}}) $ & noncommutative infinitesimals on the Hilbert space $ {\mathcal{H}} $ \\ $ {\mathcal{I}}_{\alpha} ({\mathcal{H}}) $ & noncommutative infinitesimals of order $ \alpha $ on the Hilbert space $ {\mathcal{H}} $ \\ $ {\mathcal{D}}(M) $ & classical probability distributions over M \\ $ {\mathcal{D}} ({\mathcal{H}}) $ & density operators over the Hilbert space $ {\mathcal{H}} $ \\ $ D_{T} ( \vec{p}^{(A)} , \vec{p}^{(B)} ) $ & classical trace distance among $ \vec{p}^{(A)} $ and $ \vec{p}^{(B)} $ \\ $ D_{T} ( \rho^{(A)} , \rho^{(B)} ) $ & quantum trace distance among $ \rho^{(A)} $ and $ \rho^{(B)} $ \\ $ F ( \vec{p}^{(A)} , \vec{p}^{(B)} ) $ & classical fidelity among $ \vec{p}^{(A)} $ and $ \vec{p}^{(B)} $ \\ $ F ( \rho^{(A)} , \rho^{(B)} ) $ & quantum fidelity among $ \rho^{(A)} $ and $ \rho^{(B)} $ \\ $ D_{A} ( \vec{p}^{(A)} , \vec{p}^{(B)} ) $ & classical angle distance among $ \vec{p}^{(A)} $ and $ \vec{p}^{(B)} $ \\ $ D_{A} ( \rho^{(A)} , \rho^{(B)} ) $ & quantum angle distance among $ \rho^{(A)} $ and $ \rho^{(B)} $ \\ $ A_{+} $ & positive part of the $ \star $-algebra A \\ $ A_{p.s.d} $ & part with discrete spectrum of the $ C^{\star} $-algebra A \\ $ A_{sa} $ & self-adjoint part of the $ \star $-algebra A \\ $ PUR( \rho \, , \, {\mathcal{H}} ) $ & purifications of the density operator $ \rho $ w.r.t. the Hilbert space $ {\mathcal{H}} $ \\ $ {\mathcal{U}}(A) $ & unitary group of the $ \star $-algebra A \\ $ {\mathcal{P}}(A) $ & projections of the $ \star $-algebra A \\ $ QL(A) $ & quantum logic of the $W^{\star} $-algebra A \\ $ S(A) $ & states on the $ W^{\star} $-algebra A \\ $ S(A)_{n} $ & normal states on the $ W^{\star} $-algebra A \\ $ \rho_{\omega} $ & density operator of the normal state $ \omega $ \\ $ \omega_{\mu} $ & state of the classical probability measure $ \mu $ \\ $ \Xi(A) $ & pure states on the $ W^{\star} $-algebra A \\ $ POINTS(A) $ & points on the $ W^{\star} $-algebra A \\ $ Sp(a) $ & spectrum of a \\ $ S_{\tau} ( A ) $ & $ \tau $ - invariant states on the $ W^{\star} $-algebra A \\ $ \Xi_{\tau} ( A ) $ & $ \tau $ - invariant pure states on the $ W^{\star} $-algebra A \\ $ \Delta_{\omega}(a) $ & dispersion of the state $ \omega $ on the element a of the $ W^{\star} $-algebra A \\ $ ( \mathcal{H}_{\omega} \, , \, \pi_{\omega} \, , \, | \Omega_{\omega} > ) $ & GNS-representation of the $C^{\star}$-algebra A w.r.t. the state $ \omega $ \\ $ AUT(A) $ & automorphisms of the $ W^{\star} $-algebra A \\ $ INN(A) $ & inner automorphisms of the $ W^{\star} $-algebra A \\ $ OUT(A) $ & outer automorphisms of the $ W^{\star} $-algebra A \\ \hline \end{tabular} \newpage \begin{tabular}{|c|c|} % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... $ GR-AUT( G \, , \, A) $ & automorphisms' groups of A representing G \\ $ GR-INN( G \, , \, A) $ & inner automorphisms' groups of A representing G \\ $ GR-OUT( G \, , \, A) $ & outer automorphisms' groups of A representing G \\ $ CPU(A,B) $ & channels from the $ W^{\star} $-algebra A to the $ W^{\star} $-algebra B \\ $ CPU(A) $ & channels on the $ W^{\star} $-algebra A \\ $ \alpha_{\star} $ & dual of the channel $ \alpha $ \\ $ OPU(A) $ & operational partition of unity over the $ W^{\star} $-algebra A \\ $ \{ \alpha_{i}( {\mathcal{V}}) \} $ & channels' set of the operational partition of unity $ {\mathcal{V}} $ \\ $ R ( {\mathcal{V}} ) $ & reduction channel of the operational partition of unity $ {\mathcal{V}} $ \\ $ A' $ & commutant of the Von Neumann algebra A \\ $ {\mathcal{Z}}(A) $ & centre of the Von Neumann algebra A \\ R & hyperfinite $ II_{1} $-type factor \\ $ R_{\lambda} $ & hyperfinite $ III_{\lambda} $-type factor $ ( 0 \, < \, \lambda \, < \, 1 ) $ \\ $ cardinality_{NC} (A) $ & noncommutative cardinality of the noncommutative set A \\ $ \Sigma_{NC} $ & noncommutative binary alphabet \\ $ \Sigma_{NC}^{\star} $ & noncommutative space of qubits' strings \\ $ \Sigma_{NC}^{\infty} $ & noncommutative space of qubits' sequences \\ $ M_{n} (a) $ & $ n^{th} $ moment of the algebraic random variable a \\ $ E (a) $ & expectation value of the algebraic random variable a \\ $ Var(a) $ & variance of the algebraic random variable a \\ $ Z_{a} $ & characteristic function of the algebraic random variable a \\ $ \mu_{a} $ & classical probability measure of the self-adjoint algebraic random variable a \\ $ v_{a} $ & result of the measurement of the self-adjoint algebraic random variable a \\ $ ZQ_{a}(t) $ & characteristic function of the noncommutative random variable a \\ $ ZC_{Ap}(t) $ & characteristic function of the classical approximation Ap \\ $ END( \, A \, , \, \omega \, ) $ & endomorphisms of the algebraic probability space $ ( \, A \, , \, \omega \, ) $ \\ $ AUT( \, A \, , \, \omega \, ) $ & automorphism of the algebraic probability space $ ( \, A \, , \, \omega \, ) $ \\ $ tr_{\omega} $ & Dixmier trace \\ $ O(n) $ & $ n^{th} $ orthogonal group \\ $ Spin(n) $ & $ n^{th} $ spin group \\ $ \nabla $ & Levi-Civita connection of the (pseudo)riemannian manifold $ ( M \, , \, g ) $ \\ $ \triangle_{g} $ & Laplace-Beltrami operator on the (pseudo)riemannian manifold $ ( M \, , \, g ) $ \\ $ d \mu (g) $ & metric measure of the (pseudo)riemannian manifold $ ( M \, , \, g ) $ \\ $ Is[ ( M \, , \, g )] $ & isometries' group of the (pseudo)riemannian manifold $ ( M \, , \, g ) $ \\ $ \Gamma ( M , E ) $ & sections of the fibre bundle $ E \, \stackrel{\pi}{\rightarrow} \, M $ \\ $ O(M) \, \stackrel{\pi}{\rightarrow} \, M $ & orthonormal frame bundle of the riemannian manifold $ ( M \, , \, g ) $ \\ $ S(M) \, \stackrel{\pi}{\rightarrow} \, M $ & spin bundle on the spin manifold $ ( M \, , \, g ) $ \\ $ C(M) \, \stackrel{\pi}{\rightarrow} \, M $ & Clifford bundle on the spin manifold $ ( M \, , \, g ) $ \\ $ \int_{NC} $ & noncommutative integral on the spectral triple $ ( A \, , \, {\mathcal{H}} \, , \, D ) $ \\ $ d_{NC} $ & noncommutative differential on the spectral triple $ ( A \, , \, {\mathcal{H}} \, , \, D ) $ \\ $ J[ p(z) ] $ & Julia set of the polynomial p(z) on the complex field \\ $ d \Lambda_{D} $ & Hausdorff measure on a set with Hausdorff dimension D \\ $ {\mathcal{M}} $ & Mandelbrot's set \\ $ d ( \omega_{1} , \omega_{2} ) $ & noncommutative geodesic distance between two states \\ $ ( \, D \omega_{1} \, : \, D \omega_{1} \, )_{t} $ & noncommutative Radon-Nikodym derivative between two states \\ $ \sigma^{\omega}_{t} $ & modular group of the state $ \omega $ \\ $ < \chi \, | \, {\mathcal{R}} > $ & presentation with generating system $ \chi $ and defining relators $ {\mathcal{R}} $ \\ \hline \end{tabular} \newpage \begin{tabular}{|c|c|} % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... $ F_{n} $ & free group of rank n \\ $ l^{2}(G) $ & Hilbert space of the discrete group G \\ $ {\mathcal{L}} (G) $ & left group Von Neumann algebra of the discrete group G \\ $ {\mathcal{R}} (G) $ & right group Von Neumann algebra of the discrete group G \\ $ C_{n} $ & $ n^{th} $ Catalan number \\ $ CSM ( M , N ) $ & classical statistical model w.r.t M and N \\ $ g_{CSM ( M , N )} $ & Fisher-Rao riemannian metric w.r.t. CSM ( M , N ) \\ $ \hat{\Pi}_{random} $ & Coleman-Lesniewski's operator \\ $ I_{Q} ( | \psi > ) $ & Svozil's quantum algorithmic information of $ | \psi > $ w.r.t. Q \\ $ {\mathcal{P}}_{C} (A) $ & commutative predicates over the $ W^{\star}$-algebra A \\ $ {\mathcal{P}}_{NC} (A) $ & noncommutative predicates over the $ W^{\star}$-algebra A \\ $ {\mathcal{P}}_{C}^{TYPICAL} (APS) $ & typical commutative properties of APS \\ $ {\mathcal{P}}_{NC}^{TYPICAL} (APS) $ & typical noncommutative properties of APS \\ $ KOLMOGOROV_{C}(APS) $ & Kolmogorov commutatively-random elements of APS \\ $ KOLMOGOROV_{NC}(APS) $ & Kolmogorov noncommutatively-random elements of APS \\ $ {\mathcal{L}}_{RANDOMNESS}^{C} (APS) $ & commutative laws of randomness of APS \\ $ {\mathcal{L}}_{RANDOMNESS}^{C} (APS) $ & noncommutative laws of randomness of APS \\ $ RANDOM( \Sigma_{NC}^{\infty} ) $ & random sequences of qubits \\ $ [ G \, , \, G ] $ & commutator subgroup of the group G \\ $ G_{1} \, \star \, G_{2} $ & free product of the groups $ G_{1} $ and $ G_{2} $ \\ $ A_{1} \, \star \, A_{2} $ & free product of the algebraic spaces $ A_{1} $ and $ A_{2} $ \\ $ ( A_{1} , \omega_{1} ) \, \star \, ( A_{2} , \omega_{2} ) $ & free product of $ ( A_{1} , \omega_{1} ) $ and $ ( A_{2} , \omega_{2} ) $ \\ ENSEMBLE[ CPS \, , \, n ] & ensemble of random matrices of order n w.r.t. CPS \\ $ \mu_{emp} (a) $ & empirical eigenvalue distribution of the random matrix a \\ $ \mu_{mean} (a) $ & mean eigenvalue distribution of the random matrix a \\ $ S_{Araki} ( \omega_{1} \, , \, \omega_{2} ) $ & Araki's relative entropy of $ \omega_{1} $ w.r.t. $ \omega_{2} $ \\ $ S( \omega ) $ & entropy of the state $ \omega $ \\ $ H_{\omega}(A) $ & entropy of the sub-$W^{\star}$-algebra A w.r.t. the state $ \omega $ \\ $ H_{\omega}(\alpha) $ & entropy of the the channel $ \alpha $ w.r.t. the state $ \omega $ \\ $ I( \omega \, ; \, \alpha ) $ & mutual entropy of the state $ \omega $ and the channel $ \alpha $ \\ $ DEC( \omega ) $ & decompositions of the state $ \omega $ \\ $ DEC_{EXT} ( \omega ) $ & extremal decompositions of the state $ \omega $ \\ $ DEC_{\bot} ( \omega ) $ & orthogonal decompositions of the state $ \omega $ \\ $ DEC_{Schatten} ( \omega ) $ & Schatten's decompositions of the normal state $ \omega $ \\ $ I_{acc} ( {\mathcal{E}} ) $ & classical accessible information information of the decomposition $ {\mathcal{E}} $ \\ $ I_{Holevo} ( {\mathcal{E}} ) $ & Holevo's information of the decomposition $ {\mathcal{E}} $ \\ n-GOE & gaussian orthogonal ensemble of order n \\ n-GUE & gaussian unitary ensemble of order n \\ $ gauss(D , \vec{m} , \hat{C} ; \vec{x} ) $ & D-dimensional gaussian measure of mean $ \vec{m} $ and covariance $ \hat{C} $ \\ $ gauss_{STANDARD} $ & standard gaussian measure \\ $ sc(m ,r ; x ) $ & semi-circle measure of mean m and variance $ \frac{r^{2}}{4} $ \\ $ sc_{STANDARD} $ & standard semi-circle measure \\ \hline \end{tabular} \newpage \begin{tabular}{|c|c|} % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... $ S_{Bennett} (P) $ & Bennett's entropy of the distribution P \\ $ S_{Zurek} (\rho) $ & Zurek's entropy of the density matrix $ \rho $ \\ $ S_{therm} ( \omega ) $ & thermodynamical entropy of the state $ \omega $ \\ $ S_{\text{double approach}} ( \omega ) $ & double approach entropy of the state $ \omega $ \\ $ I_{skew} ( \rho , a ) $ & skew information of the density matrix $ \rho $ w.r.t. the operator a \\ $ REC_{O} $ & recursivity in the oracle O \\ $ f \, \leq_{T} \, g $ & f is Turing reducible to g \\ $ f \, \sim_{T} \, g $ & f is Turing equivalent to g \\ $ ( {\mathcal{D}}_{T} \, , \, \leq_{T} ) $ & Turing degrees \\ $ I^{-}(S) $ & chronological past of the space-time's region's S \\ $ I^{+}(S) $ & chronological future of the space-time's region's S \\ $ J^{-}(S) $ & causal past of the space-time's region's S \\ $ J^{+}(S) $ & causal future of the space-time's region's S \\ $ D^{-}(S) $ & past domain of dependence of the space-time's region's S \\ $ D^{+}(S) $ & future domain of dependence of the space-time's region's S \\ $ D(S) $ & domain of dependence of the space-time's region's S \\ $ \approx_{Dirac} $ & weak equality \\ $ [ a \, , \, b ]_{EFF} $ & effective commutator of a and b \\ $ I^{(EFF)}_{skew} ( \rho \, , \, a ) $ & effective skew-information of $ \rho $ w.r.t. a \\ $ r-\lim_{n \rightarrow \infty} $ & recursive limit for $ n \, \rightarrow \, \infty $ \\ $ REC_{Nielsen} (A) $ & Nielsen-computable part of the $ W^{\star}$-algebra A \\ $ COMP-ST(B) $ & computability structures on the Banach space B \\ $ REC_{Pour \; El} (B , {\mathcal{S}}) $ & Pour-El computable vectors of B w.r.t. $ {\mathcal{S}} $ \\ $ REC_{Pour \; El}-{\mathcal{O}}( {\mathcal{H}}) $ & effectively determined linear operators on $ {\mathcal{H}} $ w.r.t. $ {\mathcal{S}} $ \\ $ Bloch ( \vec{r} ) $ & one qubit density operator w.r.t. the Bloch-sphere's vector $ \vec{r}$ \\ L(G) & language generated by the Chomsky's grammar G \\ FIN & finite languages \\ REG & regular languages \\ LIN & linear languages \\ CF & context-free languages \\ CS & context-sensitive languages \\ RE & recursively enumerable languages \\ IGUS & information gathering and using system \\ PRG & pseudorandom number generator \\ r.e. & recursively enumerable \\ w.r.t. & with respect to \\ l.h.s. & left-hand side \\ r.h.s. & right-hand side \\ iff & if and only if \\ i.e. & id est \\ e.g. & exempli gratia \\ \hline \end{tabular} \newpage \section{Introduction} \label{sec:Introduction} The new exciting research field of Quantum Computation has opened a cross-fertilization area among Theoretical Physics and Theoretical Computer Science that, beside the intrinsic technological difficulties in the physical implementation essentially owed to a not-sufficient technological ability in contrasting decoherence, is expected to be a strategic point for developments in both fields \cite{Preskill-98}, \cite{Nielsen-Chuang-00}, \cite{Barndorff-Nielsen-Gill-Jupp-01}, \cite{Gruska-01}. From the other side Quantum Computation Theory, concerning the algorithmic evolution of quantum information, may be seen as a sub-discipline of Quantum Information Theory, a research field that, in spite of its recent exciting developments, is a very older object of investigation in Mathematical Physics \cite{Ohya-Petz-93}, \cite{Ingarden-Kossakowski-Ohya-97}. From a foundational perspective the first natural question is: \begin{center} \textbf{What is quantum information?} \end{center} \smallskip Such an innocent question is, surprisingly, still open. \smallskip The more reasonable way of proceeding to answer this question could consist in following the same footsteps Classical Information Theory undertook to become a well-established mathematical theory \cite{Khinchin-57}, \cite{Billingsley-65}, \cite{Ihara-93},\cite{Kakihara-99} of common engeneering application \cite{Cover-Thomas-91}. Though the invention of Information Theory must be tributed with no doubt to Claude E. Shannon's 1948 paper \textit{"The Mathematical Theory of Communication"} \cite{Shannon-Weaver-71} the mathematical foundation of the concept of \textbf{classical information} was given, among the fifthies and the sixties, by the great mathematician Andrei Nicolaevich Kolmogorov \cite{Shiryayev-94}, \cite{AMS-LMS-00}. \medskip He observed that there exist three conceptually different ways of approaching the problem of defining the notion of \textbf{amount of information}: \begin{enumerate} \item the \textbf{combinatorial approach} \item the \textbf{probabilistic approach} \item the \textbf{algorithmic approach} \end{enumerate} \medskip The \textbf{combinatorial approach} furnishes a definition of the information content of an object that is \textbf{contextual}, i.e. depends from the particular context (collection of objects) in which such an object is considered, but is \textbf{weight independent}, i.e. it doesn't depend on the specification of a way of weighting the contribution of different elements of such context. So, given an object x belonging to a set X of N elements (the context) the \textbf{combinatorial approach}, invented by R. Hartley in 1928, defines the amount of information of x simply as: \begin{equation} I_{combinatorial} (x) \; := \; \log_{2} N \end{equation} Let us suppose, for example that x is a n-letter word in an alphabet of s letters containing $ m_{i} $ occurences of the $ i^{th} $ letter ($ m_{1} + \cdots + m_{s} \, = \, n $). Since there are: \begin{equation} C( m_{1}, \cdots , m_{s}) \; := \; \frac{n !}{ m_{1} ! \cdots m_{s} ! } \end{equation} words of this kind, one has that: \begin{equation} I_{combinatorial} (x) \; = \; \log_{2} C( m_{1}, \cdots , m_{s}) \end{equation} As $ n, m_{1} , \cdots m_{s} $ tend to infinity, Stirling's asymptotic formula implies that: \begin{equation} \label{eq:asymptotic combinatorial information} I_{combinatorial} (x) \; \sim \; \sum_{i=1}^{s} \frac{ m_{i} }{n} \log_{2} \frac{ m_{i} }{n} \end{equation} \medskip The \textbf{probabilistic approach} furnishes a definition of the information content of an object that is both \textbf{contextual} and \textbf{weight dependent}. So given an object x belonging to a set X of N elements (the context) such the the $ i^{th} $ element is considered with weight (probability) $ p_{i} $ , the \textbf{probabilistic approach}, that invented by Shannon in 1948 and often considered as Classical Information Theory tout court, defines the amount of information of x simply as: \begin{equation} \label{eq:probabilistic information} I_{probabilistic} (x) \; := \; - \sum_{i=1}^{N} p_{i} \log_{2} p_{i} \end{equation} It must be noted, at this point, that the asymptotic formula eq.\ref{eq:asymptotic combinatorial information} can be obtained, in the probabilistic approach by eq.\ref{eq:probabilistic information} applying the Law of Large Numbers. Anyway, at this point, Kolmogorov underlines the importance that such a result can be obtained getting rid of the \textbf{weight dependence}, observing that it is precisely what he guaranteed for other two important notions he introduced time before, namely the \textbf{$\epsilon$-entropy} $H_{\epsilon}(K) $ and the \textbf{$\epsilon$-capacity} of compact classes of functions describing, respectively, the amount of information necessary for distinguishing some individual function in the class of functions K and the amount of information that can be coded by elements of K under the condition that elements of K no closer than $ \epsilon $ to each other can be reliably distinguished. In the same way Kolmogorov stressed the importance of getting-rid of the \textbf{context dependence}, i.e. to find an \textbf{intrinsic} notion of the amount of information of an object. This led him to introduce the \textbf{algorithmic approach} that is, indeed, both \textbf{weight independent} and \textbf{context independent}: in the \textbf{algorithmic approach} the amount of information of an object x with respect to a given computer C is defined as the length of the shortest program for C computing (i.e. algorithmically-describing ) x: \begin{equation} \label{eq:naife algorithmic information} I_{algorithmic} ( C ; x) \; := \; \begin{cases} \min \{ length(p) , C(p) = x \} & \text{if x is computable by the computer C}, \\ + \infty & \text{otherwise}. \end{cases} \end{equation} The independence of this notion from the particular computer C is then established by Kolmogorov through the proof of the so called \textbf{Invariance Theorem} certifying the existence of \textbf{optimal computers}, i.e. of computers that, up to an object-independent constant, give algorithmic-descriptions always shorter of those given by any other computer. \smallskip Kolmogorov, the father of the usual, standard, measure-theoretic axiomatization, stressed from the beginning the conceptual importance of such an \textbf{intrinsic} definition of the informational-amount of an object for the same Foundation of Probability Theory, i.e. for the explanation why Probability Theory applies to reality. The key point is that the \textbf{intrinsic nature} of the algorithmic definition of information allows to address the issue of giving an \textbf{intrinsic} characterization of randomness: an algorithmically-random object x is, informally speaking, an \textbf{algorithmically-incompressible} object, i.e. an object whose more concise algorithmic-description is its same assignation. So the grown up theory concerning the algorithmic approach to information, Algorithmic Information Theory from here and beyond, appeared from the beginning as the corner-stone for an alternative Algorithmic Foundation of Classical Probability Theory \cite{Chaitin-87}, \cite{Van-Lambalgen-87}, \cite{Calude-94}, \cite{Li-Vitanyi-97}. \smallskip Later, especially by the work of Cristian Calude, Gregory Chaitin and the Auckland's Center of Discrete Mathematics and Theoretical Computer Science, Algorithmic Information Theory revealed soon an even more fundamental rule in the Foundations of Mathematics, furnishing an extraordinarily clear information-theoretic explanation of the mathematical phenomenon of Incompleteness \cite{Odifreddi-89} (Chaitin's First Undecidability Theorem states that a formal system can't decide statements involving an algorithmic-information's amount higher than its own algorithmic-informational content for more than a fixed constant, implying the recursive undecidability of algorithmic randomness), defining the notion of Halting Probability codifying in optimal way all the undecidabilities of Mathematics (the knowledge of the first n cbits in the binary expansion of Chaitin's $ \Omega $ number would allow to decide all the n-cbit mathematical statements), stating precise bounds on its determination (Chaitin's Second Undecidability Theorem states that a formal system can't decide more than a finite number of digits in the binary expansion of $ \Omega $, such a result having been recentely streghtened by R.M. Solovay through the proof that, by a proper choice of the fixed Chaitin Universal Computer and considering as formal system the Zermelo-Fraenkel axiomatic system endowed with the Axiom of Choice, this finite number of digits reduces even to zero) and, last but not least, showing that Randomness is a pervasive phaenomenon in Pure Mathematics through a paradigmatical example, i.e. shelding new light on Jones and Matjasevic's proof that Hilbert's Tenth Problem (i.e. the problem of finding an algorithm deciding whether an arbitrary Diophantine equation has integer solutions) is undecidable by the proof of the existence of a one integer parameter, let's call it k, exponential diophantine equation such that to decide if it has a finite number of integer solutions is equivalent to decide the $k^{th}$ cbit of the Halting Probability \cite{Bennett-88} \cite{Chaitin-87}, \cite{Chaitin-90}, \cite{Chaitin-98}, \cite{Chaitin-99}, \cite{Chaitin-01}, \cite{Solovay-00}. \bigskip Furthermore Algorithmic Information Theory appeared soon to play a key rule in the Theory of Chaotic Dynamical Systems: in 1958 Kolmogorov introduced (only for K-systems, the generalization for arbitrary dynamical systems having being furnished later by Ya. Sinai) a notion that would have played a key rule for the solution of the problem of giving a metric classification of dynamical systems (that is the problem of finding a complete set of invariants that imply a metric isomorphism between dynamical systems): the metric entropy of a dynamical system, characterizing the maximal asymptotic rate of information obtained through a coarse-grained observation of dynamics; a dynamical system is called chaotic if it has strictly positive metric entropy (or Kolmogorov-Sinai entropy as such notion is more often called). For the link existing between probabilistic information and probabilistically expected algorithmic information it appeared, then, intuitive that the characterization of chaoticity in terms of the probabilistic approach to information should have a counterpart in terms of the algorithmic approach: a first formalization of such a link was established by A.A. Brudno \cite{Brudno-78}, \cite{Brudno-83}, \cite{Alekseev-Yakobson-1981} by the proof of a theorem (usually called Brudno's Theorem) stating that the Kolmogorov-Sinai entropy of a dynamical system is equal to the asympotic rate of \textbf{simple algorithmic information} of almost all its trajectories. The importance of such a link was later stressed with particular emphasis by Joseph Ford who advocated strongly what he called an Algorithmic Approach to Chaos Theory \cite{Ford-92}. It must be said, anyway, that since the version of classical algorithmic information giving rise to the correct characterization of classical algorithmic randomness is not \textbf{simple algorithmic entropy} but \textbf{prefix algorithmic entropy}, the Algorithmic Approach to Chaos Theory is equivalent to the usual one only in a weak sense as we will extensively discuss. \smallskip The most important reason why Algorithmic Information Theory is of physical relevance lies, anyway, in Thermodynamics. Many generations of physicists has been educated that the correct exorcism of Maxwell's demon \cite{Maxwell-71} was the Leon's Brilloiun one \cite{Brillouin-90}: the \textbf{acquisition of information} on the velocity of the molecules by the demon is responsible of the fact that the Second Law of Thermodynamics is not violated. The recent developments of the Thermodynamics of Computation \cite{Feynman-96}, \cite{Bennett-90b}, has shown, anyway, that Brillouin's exorcism doesn't work: by Landauer's Principle \cite{Landauer-90a} such an information's acquisition process may be realized in a thermodynamically reversible way. The correct exorcism was, instead proposed by Charles Bennett \cite{Bennett-90a}: it is the \textbf{erasure of information} by the demon that cannot e accomplished in a thermodynamically reversible way and is responsible of the preservation of the Second Law. This has, anyway, dramatic conseguence concerning the same Foundations of Statistical Mechanics: introducing the issue concerning the compatibility between the time-reversibility of motions'-equation and the phenomenological time-irreversibility of thermodynamics with Ludwig Boltzmann's own words: \begin{center} \textit{"If therefore we conceive of the world as an enormously large mechanical system composed of an enormously large number of atoms, which starts from a completelly ordered initial state, and even at present is still in a substantially ordered state, then we obtain consequences which actually agree with the observed facts; although this conception involves, from a purely theoretical - I might say philosophical - standpoint, certain new aspects with contradicts general thermodynamics based on a purely phenomenological viewpoint. General thermodynamics proceeds from the fact that, as far as we can tell from our experience up to now, all natural processes are irreversible. Hence according to the principles of phenomenology, the general thermodynamics of the second law is formulated in such a way that the unconditional irreversibility of all natural process is asserted as a so-called axiom, just as general physics based on a purely phenomenological standpoint asserts the unconditional divisibility of matter without limits as an axiom". From the section 89 of \cite{Boltzmann-95}} \end{center} let us observe that most of the answers it has received, such as the one authoritatively supported by Giovanni Gallavotti seeing in Lanford's Theorem a mathematical formalization and confirmation of Boltzmann's point of view that no inconsistency exists owing to the not observability of the time-scale on which reversibility manifests \cite{Gallavotti-99}, agree in a thing: the link between the thermodynamical entropy and the state of a dynamical system is given by the \textbf{probabilistic information} of that state. As it has been strongly supported by Wojciech Zurek \cite{Zurek-89}, \cite{Zurek-90a}, \cite{Zurek-90b}, \cite{Zurek-99} Bennett's exorcism ultimatively implies that in presence of a particular kind of information gathering and using systems (IGUS), also the \textbf{algorithmic information} of the state contribute to the thermodynamical entropy and has, conseguentially, to be taken into account. \bigskip As far as Quantum Information Theory is concerned, the whole Kolmogorovian analysis concerning the three possible approaches to Information Theory may be rephrased with no variation. Anyway, nowadays, while the probabilistic approach has received a massive attention, resulting in a theory developed almost as much as the classical Shannon's theory, the situation is radically different for the combinatorial as well as for the algorithmic approach where all is available is not so much more than a plethora of attempts. The algorithmic approach to Quantum Information Theory, for its context-independence as well as for its weight-independence, is of particular importance for the mathematical foundations of such a subject. \medskip The organization of this thesis is the following: \begin{itemize} \item In part\ref{part:Equivalent characterizations of classical algorithmic randomness} we review the various equivalent characterizations of classical-algorithmic randomness \item In part\ref{part:The road for quantum algorithmic randomness} the issue of formalizing the notion of quantum algorithmic randomness in the framework of Quantum Algorithmic Information Theory is analyzed \item In part\ref{part:Classical Algorithmic Information Theory of the results of quantum measurements} the complementary issue of analyzing the classical algorithmic information status of quantum-measurements' results is discussed \end{itemize} \part{Equivalent characterizations of classical algorithmic randomness} \label{part:Equivalent characterizations of classical algorithmic randomness} \newpage \chapter{Classical algorithmic randomness as classical algorithmic incompressibility} \label{chap:Classical algorithmic randomness as classical algorithmic incompressibility} \section{The distinction between mathematical-classicality and physical-classicality} \label{sec:The distinction between mathematical-classicality and physical-classicality} The attribute \textbf{classicality} is used by two different scientific communities with different meanings: \begin{itemize} \item it is usually used by Theoretical Physicists to express that some physical system obeys the laws of Classical Mechanics; this is, for example the acception of the adjective \textbf{classical} intended in the title of the first two volumes \textit{"Classical Dynamical Systems"} and \textit{"Classical Field Theory"} \cite{Thirring-97} of Walter Thirring's monography \textit{"A Course in Mathematical Physics"} \item it is usually used by logico-mathematicians to express the part of a theory concerning only mathematical objects with cardinality less or equal to $ \aleph_{0} $; this is, for example, the acception of the adjective \textbf{classical} intended in the title \textit{"Classical Recursion Theory"} of Piergiorgio Odifreddi's monography \cite{Odifreddi-89}, \cite{Odifreddi-99a} \end{itemize} Unfortunately such a double acception of the term \textbf{classical} have generated many confusions in the literature belonging to the intersection of the two disciplines. At a foundational level the generated confusion may be seen as a confusion between the \textbf{subject} and the \textbf{object} of a computational process, i.e. between the \textbf{attributes of the computational device} and the \textbf{attributes of the computed mathematical objects}. Hence some property (classicality/quantisticality i.e. commutativity/noncommutativity) is used in two undistinguished (and often interchanged) acceptions according to it refers: \begin{itemize} \item to the \textbf{subject of the computation}, i.e. to the computational device \item to the \textbf{object of the computation}, i.e. to the computed mathematical objects \end{itemize} \smallskip An elegant way of avoiding this kind of mistakes is to pursue the following prescription: any issue of Computability Theory must analyze separetely each cell of the following: \medskip \begin{diagram}\label{di:diagram of computation} \end{diagram} DIAGRAM OF COMPUTATION: \begin{tabular}{|c|c|c|c|} % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... $ \frac{OBJECT}{SUBJECT} $ & $C_{M}$ & $NC_{M}$ \\ $C_{\Phi}$ & $\cdot_{11}$ & $\cdot_{12}$ \\ $NC_{\Phi}$ & $\cdot_{21}$ & $\cdot_{22}$ \\ \hline \end{tabular} \medskip with: \begin{description} \item[$C_{M}$ :] MATHEMATICALLY CLASSICAL \item[$NC_{M}$:] MATHEMATICALLY NONCLASSICAL \item[$C_{\Phi}$:] PHYSICALLY CLASSICAL \item[$NC_{\Phi}$:] PHYSICALLY NONCLASSICAL \end{description} \smallskip Let us consider, first of all, the following issue: \textmd{$ 1^{th}$ ISSUE: WHAT IS COMPUTABLE ?} \begin{itemize} \item $cell_{11} \; : \; C_{M} \, \cap \, C_{\Phi} $ There is complete agreement in the scientific community that, as to the computation by \textbf{physically classical computers} of the following set of functions: \begin{definition} \end{definition} MATHEMATICALLY CLASSICAL FUNCTIONS: (partial) functions on sets $ S \, : \, card(S) \, \leq \, \aleph_{0}$ \textbf{Church-Turing's Thesis} holds leading to the identification of the computable (partial) functions with the (partial) recursive functions \cite{Odifreddi-89}, \cite{Odifreddi-96} that we will now define. Introducing a notation we will adopt from here and beyond, we will denote the computability attribute relative to the cell $ cell_{i j} $ of the diagram\ref{di:diagram of computation} by the symbol $cell_{i j} - \Delta_{0}^{0} $. For example the above statement may be rephrased saying that the set $ C_{M} - C_{\Phi} - \Delta_{0}^{0} -\stackrel{ \circ } {MAP}(S,S) $ is the set of all the partial recursive functions over S. Let, clarify, first of all, what we mean by a partial function: a \textbf{total} (i.e. ordinary) $ f \, : \, A \, \rightarrow \, B $ is a rule associating to every element x of the set A an element f(x) of the set B: \begin{equation*} x \in A \; \stackrel{f}{\rightarrow} \; f(x) \in B \end{equation*} We will indicate the set of all the total functions from a set A to a set B by MAP(A,B). A \textbf{partial function} $ f \, : \, A \stackrel{\circ}{\rightarrow} \, B $ is a rule associating to each element x of a certain subset $ HALTING(f) \subseteq A $ of A, said the \textbf{halting set of f}, an element f(x) of the set B: \begin{equation*} x \in HALTING(f) \; \stackrel{f}{\rightarrow} \; f(x) \in B \end{equation*} We will say that: \begin{definition} \end{definition} f HALTS ON $ x\ \in A \; ( f(x) \downarrow ) $: \begin{equation} x \; \in \; HALTING(f) \end{equation} \begin{definition} \end{definition} f DOESN'T HALT ON $ x\ \in A \; ( f(x) \uparrow ) $: \begin{equation} x \; \notin \; HALTING(f) \end{equation} We will indicate the set of all the partial functions from a set A to a set B by $ \stackrel{\circ}{MAP}(A,B) $. Given two partial functions $ f_{1} , f_{2} \, \in \, \stackrel{\circ}{MAP}(A,B) $: \begin{definition} \end{definition} $ f_{1} $ IS EQUAL TO $ f_{2} \; ( f_{1} \, = \, f_{2} ) $: \begin{equation} ( HALTING( f_{1} ) \, = \, HALTING( f_{2} ) ) \; and \; (f_{1} (x) \, = \, f_{2}(x) \; \; \forall x \in HALTING( f_{1} )) \end{equation} The language of \textbf{partial functions} is of common use in Mathematical-Logic; we adopt it, anyway, also in unusual environments: from Classical (i.e. commutative) Measure Theory (in which measures' halting sets will be suitable $ \sigma $-algebras) to Operator Theory on Hilbert spaces (in which unbounded operators' halting sets will be dense subspaces) Denoted by $ {\mathbb{N}}^{\star} \; := \; \bigcup_{n \in {\mathbb{N}}} {\mathbb{N}}^{n} $ the set of all the n-ples of natural numbers: \begin{definition} \label{def:partial recursive functions on numbers} \end{definition} CLASS OF PARTIAL RECURSIVE FUNCTIONS (ON NUMBERS) $(REC-\stackrel{\circ} {MAP} ( {\mathbb{N}}^{n} \, , \, {\mathbb{N}} ))$ the smallest class of partial functions: \begin{enumerate} \item containing the initial functions: \begin{align} {\mathcal{O}} & (x) \; := \; 0 \\ {\mathcal{S}} & (x) \; := \; x+1 \\ {\mathcal{I}}_{i}^{n} & (x_{1}, \cdots , x_{n}) \; := \; x_{i} \; \; i=1 , \cdots , n \, , \, n \in {\mathbb{N}} \end{align} \item closed under \textbf{composition}, i.e. the schema that given $ \gamma_{1} , \cdots , \gamma_{m} , \psi $ produces: \begin{equation} \varphi ( \vec{x} ) \; := \; \psi ( \gamma_{1} ( \vec{x} ) , \cdots , \gamma_{m} ( \vec{x} ) ) \end{equation} \item closed under \textbf{primitive recursion}, i.e. the schema that given $ \psi \, , \, \gamma $ produces: \begin{align} \varphi( \vec{x} , 0 ) \; & := \; \psi ( \vec{x} ) \\ \varphi( \vec{x} , y+1 ) \; & := \; \gamma ( \vec{x} , y , \phi( \vec{x}, y )) \end{align} \item closed under \textbf{unrestricted $ \mu $-recursion}, i.e. the schema that given $ \psi $ produces: \begin{equation} \varphi( \vec{x} ) \; := \; \min \{ y \, : \, ( \psi( \vec{x} , z ) \downarrow \; \forall z \leq y ) \: and \: ( \psi( \vec{x} , y ) \, = \, 0 ) \} \end{equation} where $ \varphi( \vec{x} ) \, := \, \uparrow $ if there is no such function \end{enumerate} \smallskip The more fundamental properties of partial recursive functions may be collected in the following: \begin{theorem} \label{th:Goedel's numbering of partial recursive functions} \end{theorem} G\"{O}DEL'S NUMBERING OF PARTIAL RECURSIVE FUNCTIONS: It is possible to enumerate all partial recursive functions: \begin{equation*} \varphi_{e}^{(n)} \: : \: {\mathbb{N}}^{n} \, \stackrel{\circ}{\rightarrow} \, {\mathbb{N}} \end{equation*} (where the natural number \textbf{e} is called the \textbf{G\"{o}del's number} of the $ e^{th}$ n-ary partial recursive function) in such a way that the following conditions are satisfied: \begin{itemize} \item \textbf{Universality:} there is a partial recursive function of two variables $ \varphi_{z}^{(2)}(e,x) $ such that: \begin{equation} \varphi_{z}^{(2)}(e,x) \; = \; \varphi_{e}^{(1)}(e,x) \; \; \forall x \in {\mathbb{N}} \end{equation} \item \textbf{Uniform Composition:} there is a (total) recursive function of two variables \emph{comp} such that: \begin{equation} \varphi_{comp(x,y)}^{(1)}(z) \; = \; \varphi_{x}^{(1)}( \varphi_{y}^{(1)} (z)) \; \; \forall x,y,z \in {\mathbb{N}} \end{equation} \item \textbf{Fixed Point:} For every $ m \in {\mathbb{N}}_{+} $ and every recursive function f there effectively exists an x (called the fixed point of f) such that: \begin{equation} \varphi_{x}^{(m)} \; = \; \varphi_{f(x)}^{(m)} \end{equation} \end{itemize} \smallskip It is useful to introduce the following notation concerning the domains of partial recursive functions: \begin{definition} \label{def:domains of partial recursive functions} \end{definition} \begin{equation} {\mathcal{W}}_{e}^{n} \; := \; HALTING( \varphi_{e}^{(n)}) \; \; e,n \in {\mathbb{N}} \end{equation} Given an n-ary relation $ R( x_{1} , \cdots , x_{n} ) $ on $ {\mathbb{N}} $: \begin{definition} \label{def:r.e. relations} \end{definition} R IS RECURSIVELY ENUMERABLE (R.E.): \begin{equation} \exists e \in {\mathbb{N}} \; : \; R \, = \, {\mathcal{W}}_{e}^{n} \end{equation} We will identify, from here and beyond, \textbf{sets} and \textbf{unary relations} by posing: \begin{equation} {\mathcal{W}}_{e} \; := \; {\mathcal{W}}_{e}^{1} \end{equation} Given a set $ S \subset {\mathbb{N}}^{\star} $: \begin{definition} \label{def:recursive set} \end{definition} S IS RECURSIVE: the characteristic function $ \chi_{S} $: \begin{equation}\label{eq:characteristic function of a set} \chi_{S} (x) \; := \; \begin{cases} 1 & \text{if $ x \in S $}, \\ 0 & \text{otherwise}. \end{cases} \end{equation} is a total recursive function \smallskip Clearly one has that: \begin{theorem} \label{th:recursivity is stronger than recursive enumerability} \end{theorem} RECURSIVITY IS STRONGER THAN RECURSIVE ENUMERABILITY: \begin{align*} recursivity & \; \Rightarrow \; \text{ recursive enumerability} \\ \text{ recursive enumerability} & \; \nRightarrow \; recursivity \end{align*} \smallskip \begin{remark} \label{Godel numbering and self-reference} \end{remark} G\"{O}DEL NUMBERING AND SELF-REFERENCE G\"{o}del's numbering, introduced by Kurt G\"{o}del in his his famous 1931's paper \emph{"On Formally Undecidable Propositions of the Principia Mathematica and Related Systems"} \cite{Davis-65}, is a deep concept since it creates that link between \textbf{language} and \textbf{meta-language} giving rise to self-reference and all the consequences it generates through Cantor's Diagonalization. Since recursivity is equivalent to representability in an arbitary consistent formal system extending Tarski-Montowski-Robinson Arithmetics G\"{o}del's numbering may be equivalentely seen as a way of enumerating all the logical propositions concerning natural numbers. So one has a hierarchy of levels: \begin{enumerate} \item the \textbf{objects} of investigation, i.e. natural numbers \item the \textbf{language} by which properties of the objects are described, i.e. the logical propositions concerning the objects \item the \textbf{meta-language} by which properties of the \textbf{meta-objects}, i.e the logical propositions of the language (by which properties of the objects are described) are described; we will denote by \textbf{meta-proposition} a proposition of the \textbf{meta-language} \end{enumerate} Owing to G\"{o}del numbering, a \textbf{number} plays a double rule: \begin{itemize} \item as an \textbf{object} \item as the G\"{o}del number identifying a proposition of the language, i.e. as a \textbf{meta-object} \end{itemize} This can be used to pass from \textbf{meta-language} to the \textbf{language}, simply associating to the \textbf{meta-proposition} $ \varphi_{e} (x) $ concerning the \textbf{meta-object} x, i.e. the proposition of the language with G\"{o}del number x, the \textbf{proposition} $ \varphi_{e} (x) $ concerning the \textbf{object}, i.e. the number, x and, viceversa, to pass from \textbf{language} to \textbf{meta-language}, associating to the \textbf{proposition} $ \varphi_{e}(x) $ concerning the \textbf{object}, i.e. the number, x the \textbf{meta-proposition} $ \varphi_{e} (x) $ concerning the \textbf{meta-object} x, i.e. the proposition of the language with G\"{o}del number x. But then self-reference immediately appears since $ \varphi_{e}(e) $ happens to speak about itself. \item $cell_{21} \; : \; C_{M} \, \cap \, NC_{\Phi} $ There is no universally accepted answer in the scientific community to the question if a \textbf{physically nonclassical computer} can violate Church-Turing's Thesis, i.e. can compute non-recursive \textbf{mathematically classical functions}. In particular, as far as the computation by \textbf{physically quantistical computers} of \textbf{mathematically classical functions} is concerned, the common opinion among the researchers in Quantum Computation \cite{Feynman-99}, \cite{Deutsch-85}, \cite{Jozsa-98} is that \textbf{Nonrelativistic Quantum Mechanics} and \textbf{Special-relativistic Quantum Mechanics (Local Quantum Field Theories)} don't violate Church-Turing's Thesis. It must be cited, anyway, that the opposite thesis has been asserted by various authors (cfr. \cite{Castagnoli-Rasetti-Vincenti-92}, \cite{Mitchison-Jozsa-99}, \cite{Calude-Dinneen-Svozil-00} and the paragraphs 4.12 and 4.23 of \cite{Calude-Paun-01}) Furthermore it must be observed that in the Masanao Ozawa's final formalization of Quantum Turing Machines \cite{Ozawa-98a} ( saying according, to us, the last word on the consistence's problem of Deutsch's Halting Protocol) the satisfaction of the Church-Turing's Thesis is posed by hand restricting the range of the local transition function to recursive complex numbers. We will, anyway, extensively return on this point in section\ref{sec:The problem of characterizing mathematically the notion of a quantum algorithm} Finally, when \textbf{Generally-relativistic Quantum Mechanics} (both in the form of \textbf{Quantum Gravity} and in the form of some suggested \textbf{gravitationally-modificated Quantum Mechanics}) is considered, the whole story touches the strongly debated ideas of Roger Penrose about a non-computable alteration of the quantum unitary dynamics induced by gravity \cite{Penrose-89}, \cite{Penrose-96}, \cite{Anandan-98}, \cite{Penrose-00}. \item $cell_{12} \; : \; NC_{M} \, \cap \, C_{\Phi} $ As soon as one goes out from the boundaries of $ C_{M}$-Classical Recursion Theory the almost miracolous equivalence of all the different approaches (recursivity, finitely definability, Herbrand-G\"{o}del Computability, representability in consistent formal system extending Tarski-Montowski-Robinson Arithmetics, $ \lambda$-definability in Church's $ \lambda $- Calculus, flowchart computability, computability by Classical Turing Machines, by cellular automata \cite{Odifreddi-89}, by Shepherdson-Sturgis register machines \cite{Cutland-80}, LISP computability \cite{Mc-Carthy-60}, $ \cdots $) that in such a theory manifests the strong experimental verification of Church's Thesis, dramatically disappears. Just as to Computability Theory by \textbf{physically classical computers} of (partial) functions on sets $ S \, : \, cardinality(S) \, = \, \aleph_{1}$ while many different inequivalent candidate theories have been proposed: \begin{enumerate} \item the well extablished and almost always accepted theory named Computable Analysis, generated by the studies of Grzegorczyck - Lacombe \cite{Pour-El-Richards-89} \item the theory developed by the so called Markov School in the framework of Constructive Mathematics \cite{Odifreddi-89} \item the Blum - Shub - Smale 's Theory \cite{Smale-92}, \cite{Blum-Cucker-Shub-Smale-98} \end{enumerate} The relative popularity of the issue about the concurrence of such candidate theories is owed to Penrose's question if Mandelbrot's set is recursive \cite{Penrose-89}. We will partially analyze it in section\ref{sec:Brudno algorithmic entropy versus the Uspensky abstract approach} \item $cell_{22} \; : \; NC_{M} \, \cap \, NC_{\Phi} $ It's important to realize that, contrary to what is often claimed, Church-Turing's Thesis doesn't imply that the answer to the $ 1^{th} ISSUE $ contained in the cells $cell_{12}$ and $cell_{22}$ must be equal. For example Church-Turing's Thesis is not incompatible with an hypothetical situation in which Mandelbrot's set would be $ C_{\Phi} $ - incomputable but $ NC_{\Phi} $ - computable. Though some undecidability theorems and conjectures still exist (cfr. e.g. Lloyd's arguments concerning uncomputable diagonalizations in Quantum Computation \cite{Loyd-89} as well as his general consideration about the physical limits of Computation \cite{Lloyd-01}, or Geroch and Hartle's speculations concerning the eventuality that the recursive undecidability of the Homeomorphism-problem for four-manifolds \cite{Collins-Zieschang-98} may lead to the recursive undecidability of quantizing Gravity) no general mathematically formalization has been realized yet. Particular importance has, according to us, Karl Svozil's suggestion that in Quantum Algorirhmic Information Theory there should exist undecidability theorems analogues to the classical Chaitin's ones (cfr. the problem17 of \cite{Calude-96}). \end{itemize} \newpage \section{Uspensky's abstract definition of algorithmic information} \label{sec:Uspensky's abstract definition of algorithmic information} The last contribution Andrei Nikolaevich Kolmogorov left us before dying was his forum report \textit{Algorithms and Randomness}, made with and exposed by his student Vladimir Uspensky, at the First World Congress of the Bernoulli Society (September 8-14, 1986) \cite{AMS-LMS-00}. Later Unspensky formalized the Kolmogorovian approach to Algorithmic Information Theory in a very general and elegant way we will start from \cite{Uspensky-92}, \cite{Uspensky-Semenov-93}. \begin{definition} \label{def:aggregate} \end{definition} AGGREGATE: a couple $ ( X \, , \, R ) $ such that: \begin{itemize} \item X is a set \item R, called a \textbf{concordance relation}, is a computable binary relation on X \end{itemize} \medskip \begin{remark} \label{rem:context dependence of the computability constraint} \end{remark} CONTEXT-DEPENDENCE OF THE COMPUTABILITY CONSTRAINT Let us observe that, in the definition def.\ref{def:aggregate} we have imposed a \textbf{computability constraint} without specifying its precise mathematical meaning. This has been done in order of guaranteeing the maximal generality: in the different contextes corresponding to the different cells $ cell_{ij} $ of the diagram\ref{di:diagram of computation} such a constraint is formalized by the proper $ cell_{ij} - \Delta_{0}^{0}$ condition \bigskip Given two aggregates $ A_{1} \, := \, ( X_{1} \, , \, R_{1} ) $ and $ A_{2} \, := \, ( X_{2} \, , \, R_{2} ) $ it is natural to ask under which conditions we can think to elements of $ A_{2} $ as descriptions of elements of $ A_{1} $ with respect to a proper description mode; the answer is given by the following definition: \begin{definition} \end{definition} MODE OF DESCRIPTION (OF $ A_{2} $-ELEMENTS THROUGH $ A_{1} $-ELEMENTS): a relation R between elements of $ X_{1} $ and elements of $ X_{2} $ such that: \begin{equation}\label{eq:mode of description} R_{1}( x_{1} , y_{1}) \, and \, R_{2}( x_{2} , y_{2}) \, and \, R( x_{1} , x_{2}) \; \Rightarrow \; R( y_{1} , y_{2}) \; \; \forall x_{1} , x_{2} \in X_{1} , \forall y_{1} , y_{2} \in X_{2} \end{equation} \smallskip We will denote the set of all the mode of description of $ A_{2} $-elements through $ A_{1} $-elements by $ {\mathcal{D}}( A_{1} , A_{2} ) $. \smallskip Given a mode of description R among the aggregates $ A_{1} $ and $ A_{2} $: \begin{definition} \end{definition} $ x_{2} \in X_{2}$ IS A DESCRIPTION OF $ x_{1} \in X_{1} $ THROUGH THE MODE R: \begin{equation} R( x_{1} , x_{2} ) \end{equation} \smallskip All the ingredients introduced up to this point are of pure set-theoretic nature (with some constructibility constraint). The introduction of a notion characterizing the amount of not-redundant, i.e. algorithmically incompressible, information of an object $ x_{1} \in X_{1} $ with respect to the description mode R requires the introduction of some point measure quantifying the extension of the descriptions. Let us, then, define, the following notion: \begin{definition} \end{definition} METRIC AGGREGATE: a couple $ ( A \, , \mu ) $ such that: \begin{itemize} \item $ A \, := \, ( X \, , R ) $ is an aggregate \item $ \mu $ is a point measure on A \end{itemize} \smallskip Given a metric aggregate $ A_{1} \, := \, ( X_{1} \, , \, R_{1} \, , \, \mu ) $, an aggregate $ A_{2} \, := \, ( X_{2} \, , \, R_{2} \, ) $ and a mode of description R among the aggregates $ A_{1} $ and $ A_{2} $ we can finally introduce the following basic notion: \begin{definition} \label{def:algorithmic information} \end{definition} ALGORITHMIC INFORMATION OF $ x_{2} \in X_{2} $ W.R.T. THE DESCRIPTION MODE R: \begin{equation} I_{R} ( x_{2} ) \; := \; \begin{cases} \min \{ \mu ( x_{1} ) \, : \, R( x_{1} , x_{2} ) \} & \text{if $ \exists \, x_{1} \in X_{1} \, : R( x_{1} , x_{2} )$}, \\ + \infty & \text{otherwise}. \end{cases} \end{equation} \smallskip Clearly the definition def.\ref{def:algorithmic information} depends on the particular chosen description mode R. It is clear, anyway, that the whole consistence of Algorithmic Information Theory lies on the possibility of getting-rid of such a dependence. The formalization of this issue is given by the following notions: \begin{definition} \end{definition} UNIVERSE OF DESCRIPTION OF $ A_{2} $ THROUGH $ A_{1} $: a set $ {\mathcal{R}} $ of description modes of the aggregate $ A_{2} $ through the metric aggregate $ A_{1} $: \begin{equation} {\mathcal{R}} \; \subseteq \; {\mathcal{D}}( A_{1} , A_{2} ) \end{equation} \smallskip The intuitive idea we are going to formalize is that Algorithmic Information Theory is meaningful provided the involved universes of descriptions admit optimal mode of descriptions, i.e. mode of descriptions that are always more concise of all the others, up to an object-independent additive constant. This requires the introduction of two ordering relation we will use extensively in the whole dissertation. Given two real-valued partial function $ f_{1} : A \stackrel {\circ}{\rightarrow} {\mathbb{R}} \, , \, f_{2} : A \stackrel {\circ}{\rightarrow} {\mathbb{R}} $ we will say that: \begin{definition} \label{def:addittively less or equal} \end{definition} $ f_{1} $ IS ADDITIVELY LESS OR EQUAL TO $ f_{2} $ ( $ f_{1} \, \stackrel{ + }{\leq} \, f_{2} $ ) \begin{equation} \exists c \in {\mathbb{R}}_{+} \; : \; f_{1} (x) \, \leq \, f_{2} (x) + c \; \; \forall x \in HALTING(f_{1}) \bigcap HALTING(f_{2}) \end{equation} \begin{definition} \label{def:addittively equal} \end{definition} $ f_{1} $ IS ADDITIVELY EQUAL TO $ f_{2} $ ( $ f_{1} \, \stackrel{ = }{\leq} \, f_{2} $ ) \begin{equation} f_{1} \, \stackrel{ + }{\leq} \, f_{2} \; and \; f_{2} \, \stackrel{ + }{\leq} \, f_{1} \end{equation} \begin{definition} \label{def:multiplicatively less or equal} \end{definition} $ f_{1} $ IS MULTIPLICATIVELY LESS OR EQUAL TO $ f_{2} $ ( $ f_{1} \, \stackrel { \times }{\leq} \, f_{2} $ ) \begin{equation} \exists c \in {\mathbb{R}}_{+} \; : \; f_{1} (x) \, \leq \, f_{2} (x) \times c \; \; \forall x \in HALTING(f_{1}) \bigcap HALTING(f_{2}) \end{equation} \begin{definition} \label{def:multiplicatively equal} \end{definition} $ f_{1} $ IS MULTIPLICATIVELY EQUAL TO $ f_{2} $ ( $ f_{1} \, \stackrel { \times }{=} \, f_{2} $ ) \begin{equation} f_{1} \, \stackrel{ \times }{ \leq } \, f_{2} \; and \; f_{2} \, \stackrel{ \times }{\leq} \, f_{1} \end{equation} \medskip Let us now consider an aggregate $ A_{1} $, a metric aggregate $ A_{2} $, a universe of description $ {\mathcal{R}} $ of $ A_{1} $ through $ A_{2} $ and a particular mode of description belonging to such a universe $ U \in {\mathcal{R}} $. We will say that: \begin{definition} \label{def:optimal mode of description} \end{definition} U IS OPTIMAL W.R.T. $ {\mathcal{R}} $: \begin{equation} U \; \stackrel{ + }{\leq} \; f \; \; \forall f \in {\mathcal{R}} \end{equation} We can then introduce the following notion: \begin{definition} \end{definition} ALGORITHMIC INFORMATION THEORY IS MEANINGFUL W.R.T. $ {\mathcal{R}} $: \begin{equation} \exists \; U \in {\mathcal{R}} \; optimal \end{equation} Adhering to Uspensky's terminology let us introduce the following notion: \begin{definition} \end{definition} ALGORITHMIC ENTROPY: a function I equal to the algorithmic information w.r.t. a description mode that is optimal w.r.t to some universe of description modes. \medskip In order to discuss the first fundamental examples, let us introduce some basic notions. Given a set $ \Sigma $: \begin{definition} \label{def: classical strings on an alphabet} \end{definition} SET OF THE STRINGS ON $ \Sigma $ : \begin{equation} \Sigma^{\star} \; \equiv \; \{ \lambda \} \; \bigcup \; \cup_{ k \in {\mathbb{N}}} \Sigma^{k} \end{equation} \begin{definition} \label{def: classical sequences on an alphabet} \end{definition} SET OF THE SEQUENCES ON $ \Sigma $: \begin{equation} \Sigma^{\infty} \; \equiv \; \{ \lambda \} \; \bigcup \; \{ \bar{x} : {\mathbb{N}}_{+} \, \rightarrow \, \Sigma \} \end{equation} where $ \lambda $ denotes the \textit{empty string}. Given $ \vec{x} \in \Sigma^{\star} $ let us denote by $ \vec{x}^{n} \in \Sigma^{\star} $ the string made of n repetitions of $ \vec{x} $ and by $ \vec{x} ^{\infty} \in \Sigma^{\infty} $ the sequence made of infinite repetitions of $ \vec{x} $. It is important to remark that \cite{Calude-94}: \begin{theorem} \label{th:cardinalities of strings and sequences} \end{theorem} ON THE CARDINALITIES OF STRINGS AND SEQUENCES OVER A FINITE ALPHABET \begin{hypothesis} \end{hypothesis} \begin{equation*} cardinality ( \Sigma ) \; \in \; {\mathbb{N}} \end{equation*} \begin{thesis} \end{thesis} \begin{align*} cardinality(\Sigma^{\star}) \; & = \; \aleph_{0} \\ cardinality(\Sigma^{\infty}) \; & = \; \aleph_{1} \end{align*} We will assume from here and beyond that $ \Sigma \; := \; \{ 0 ,1 \}$. The total-ordering $ 0 \; < \; 1 $ induces the following: \begin{definition} \end{definition} QUASI-LEXICOGRAPHIC ORDERING ON $\Sigma^{\star}$ \begin{multline} \lambda \, < \, 0 \, < \, 1 \, < \, 00 \, < \, 01 \, < \, \\ 10 \, < \, 11 \, < \, 000 \, < \, 001 \, < \, \cdots 111 \, < \, \cdots \end{multline} We can then introduce the following bijection: \begin{definition} \end{definition} QUASI-LEXICOGRAPHIC MAP: \begin{equation} \begin{split} string : {\mathbb{N}} & \rightarrow \Sigma^{\star} \\ string(n) \, & \, = \text{the $ n^{th} $ string in quasi-lexicographic ordering} \end{split} \end{equation} \smallskip Let us now introduce the following ordering relation on $ \Sigma^{\star} $ \begin{definition} \end{definition} PREFIX-ORDER RELATION $ <_{p} $ ON $ \Sigma^{\star} $: \begin{equation} \vec{x} <_{p} \vec{y} \; := \; \exists \vec{z} \in \Sigma^{\star} \, : \; \vec{y} = \vec{x} \cdot \vec{z} \end{equation} Give a set $ S \, \subset \, \Sigma^{\star} $ we will say that: \begin{definition} \end{definition} S IS PREFIX-FREE: \begin{equation} ( \vec{x} <_{p} \vec{y} \Rightarrow \vec{x} = \vec{y} ) \, \forall \vec{x},\vec{y} \in S \end{equation} \medskip \begin{example} \label{ex:simple algorithmic entropy} \end{example} SIMPLE ALGORITHMIC ENTROPY Let us consider the case in which $ A_{1} \; = \; A_{2} \; = \; ( {\mathbb{N}} \, , \, = \, , \, | \cdot | ) $ with: \begin{equation} | n | \; := \; | string^{- 1} (n) | \; = \; \llcorner \log_{2} ( n + 1 ) \lrcorner \end{equation} Kolmogorov started considering as universe of mode of descriptions the whole $ {\mathcal{D}}( A_{1} , A_{2} ) $. But he immediately realized that: \begin{theorem} \label{th:simple algorithmic information theory w.r.t. all the partial functions is not meaningful} \end{theorem} ALGORITHMIC INFORMATION THEORY W.R.T. $ {\mathcal{D}}( A_{1} , A_{2} ) $ IS NOT MEANINGFUL \begin{proof} Following \cite{Li-Vitanyi-97} let us us suppose by abdurdum that there exist a function $ U \in \bigcap {\mathcal{D}}( A_{1} , A_{2} )$ such that: \begin{equation} U \; \stackrel{ + }{\leq} \; f \; \; \forall f \in {\mathcal{D}} ( A_{1} \, , \, A_{2} ) \end{equation} Let us then consider an infinite sequence $ X \, := \, \{ x_{n} \in {\mathbb{N}} \}_{n \in {\mathbb{N}}} $ such that: \begin{equation} i < j \; \Rightarrow \; x_{i} < x_{j} \; \, \forall i,j \in {\mathbb{N}} \end{equation} Considered a subsequence $ Y \, := \, \{ y_{n} \in {\mathbb{N}} \}_{n \in {\mathbb{N}}} $ of the sequence X such that: \begin{equation} \log y_{n} \; < \; \frac{ \log x_{n} }{2} \; \; \forall n \in {\mathbb{N}} \end{equation} let us introduce the function $ f \in {\mathcal{D}}( A_{1} , A_{2} ) $ conciding with U everywhere but for the points of the sequence X where it is defined as: \begin{equation} f( x_{n} ) \; := \; U ( y_{n} ) \; \; \forall n \in {\mathbb{N}} \end{equation} We have clearly that: \begin{equation} cardinality ( \{ n \in {\mathbb{N}} \, : I_{f} ( n ) \, \leq \, \frac{ I_{U} ( n )}{2} \} ) \; = \; \aleph_{0} \end{equation} that contradict the absurdum hypothesis \end{proof} \medskip Theorem\ref{th:simple algorithmic information theory w.r.t. all the partial functions is not meaningful} is the first of a set of theorems we will meet in this dissertation showing that certain quantities of Algorithmic Information Theory are meaningful only by effectivizing some notion. Indeed, requiring that to describe objects must be an effective property, one is led by Church-Turing's thesis, for reasons that will be clarified in the next section, to restrict the universe of modes of descriptions to the set $ C_{M}-C_{\Phi} -\Delta_{0}^{0} [ {\mathcal{D}}( A_{1} , A_{2} )] $ of the \textbf{partial recursive ones}. Kolmogorov realized that in this way the problem was overcome proving the following \cite{Calude-94}: \begin{theorem} \label{th:invariance theorem for simple algorithmic entropy} \end{theorem} INVARIANCE THEOREM FOR SIMPLE ALGORITHMIC ENTROPY: Algorithmic Information Theory w.r.t. $ C_{M}-C_{\Phi}- \Delta_{0}^{0} - [ {\mathcal{D}}( A_{1} , A_{2} )] $ is meaningful \smallskip As we have preannounced, the resulting algorithmic entropy, w.r.t. an optimal description mode that we will call from here and beyond a \textbf{simple universal computer}, is called the \textbf{simple algorithmic entropy} and is denoted by K. \medskip \begin{example} \label{ex:monotone algorithmic entropy} \end{example} MONOTONE ALGORITHMIC ENTROPY Let us consider the case in which $ A_{1} \; = \; A_{2} \; = \; ( \Sigma^{\star} \, , \, <_{p} \, , \, | \cdot | ) $. Exactly as in the example\ref{ex:simple algorithmic entropy} it may be proved that: \begin{theorem} \label{th:monotone algorithmic information theory w.r.t. all the partial functions is not meaningful} \end{theorem} ALGORITHMIC INFORMATION THEORY W.R.T. $ {\mathcal{D}}( A_{1} , A_{2} ) $ IS NOT MEANINGFUL \smallskip but: \begin{theorem} \end{theorem} INVARIANCE THEOREM FOR MONOTONE ALGORITHMIC ENTROPY: Algorithmic Information Theory w.r.t. $ C_{M}-C_{\Phi}- \Delta_{0}^{0} - [ {\mathcal{D}}( A_{1} , A_{2} )] $ is meaningful \smallskip As we have preannounced, the resulting algorithmic entropy is called the \textbf{monotone algorithmic entropy} \medskip \begin{remark} \end{remark} FROM BINARY STRINGS TO NATURAL NUMBERS AND VICEVERSA For pure simplicity reasons we have defined simple algorithmic entropy for natural numbers and monotone algorithmic information for binary strings. By the quasi-lexicographic bijection the corrispondent notions, namely simple algorithmic entropy of strings and prefix algorithmic entropy of natural numbers are immediately obtained. For the same reason from here and beyond everything stated for $ \Sigma^{\star} $ may be immediately translated in terms of $ {\mathbb{N}} $ and viceversa. \medskip Up to now we have considered the case in which the two metric aggregates coincide. Anyway one can clearly introduce also the following mixed notions: \begin{example} \label{ex:decision algorithmic entropy} \end{example} DECISION ALGORITHMIC ENTROPY: Let us assume $ A_{1} \; = ( {\mathbb{N}} \, , \, = \, , \, | \cdot | ) $ while $ A_{2} \; = \; ( \Sigma^{\star} \, , \, <_{p} \, , \, | \cdot | )$. Exactly as in the example\ref{ex:simple algorithmic entropy} it may be proved that: \begin{theorem} \label{th:decision algorithmic information theory w.r.t. all the partial functions is not meaningful} \end{theorem} ALGORITHMIC INFORMATION THEORY W.R.T. $ {\mathcal{D}}( A_{1} , A_{2} ) $ IS NOT MEANINGFUL \smallskip but: \begin{theorem} \end{theorem} INVARIANCE THEOREM FOR DECISION ALGORITHMIC ENTROPY: Algorithmic Information Theory w.r.t. $ C_{M}-C_{\Phi}- \Delta_{0}^{0} - [ {\mathcal{D}}( A_{1} , A_{2} )] $ is meaningful \smallskip As we have preannounced, the resulting algorithmic entropy is called the \textbf{monotone algorithmic entropy} \medskip \begin{example} \label{ex:prefix algorithmic entropy} \end{example} PREFIX ALGORITHMIC ENTROPY: Let us assume $ A_{1} \; = \; ( \Sigma^{\star} \, , \, <_{p} \, , \, | \cdot | )$ while $ A_{2} \; = ( {\mathbb{N}} \, , \, = \, , \, | \cdot | ) $. Exactly as in the example\ref{ex:simple algorithmic entropy} it may be proved that: \begin{theorem} \label{th:prefix algorithmic information theory w.r.t. all the partial functions is not meaningful} \end{theorem} ALGORITHMIC INFORMATION THEORY W.R.T. $ {\mathcal{D}}( A_{1} , A_{2} ) $ IS NOT MEANINGFUL \smallskip but: \begin{theorem} \label{th:invariance theorem for prefix algorithmic entropy} \end{theorem} INVARIANCE THEOREM FOR PREFIX ALGORITHMIC ENTROPY: Algorithmic Information Theory w.r.t. $ C_{M}-C_{\Phi}- \Delta_{0}^{0} - [ {\mathcal{D}}( A_{1} , A_{2} )] $ is meaningful \smallskip As we have preannounced, the resulting algorithmic entropy, w.r.t. an optimal description mode that we will call from here and beyond a \textbf{Chaitin universal computer}, is called the \textbf{prefix algorithmic entropy} and is denoted by I. \medskip While the \textbf{decision entropy} and \textbf{monotone entropy} are of scarce utility, \textbf{simple entropy} and \textbf{prefix entropy} are of fundamental importance \newpage \section{Why prefix algorithmic entropy is better than simple algorithmic entropy} \label{sec:Why prefix entropy is better than simple entropy} Let us now compare simple algorithmic entropy and prefix algorithmic entropy. Though more intuitive, simple algorithmic entropy has a list of inconveniences that, after decades of debates among different attempts, led the scientific community to realize that the correct way of formulating Classical Algorithmic Information Theory involves prefix algorithmic entropy: \begin{enumerate} \item \textbf{classical probabilistic information}, namely \textbf{Shannon entropy}, satisfies the \textbf{subadditivity property}: \begin{equation} \label{eq:subadditivity of probabilistic information} I_{probabilistic} ( X , Y ) \; \leq \; I_{probabilistic} (X) + I_{probabilistic} (Y) \end{equation} with the equality holding iff the classical random variables X and Y are independent, where the joint probabilistic information $ I_{probabilistic} ( X , Y ) $ will be defined in section\ref{sec:From the communicational-compression of the Quantum Coding Theorems to the algorithmic-compression in Quantum Computation}. As we will see therein the subadditivity property remain preserved in the noncommutative generalization, i.e. eq.\ref{eq:subadditivity of probabilistic information} holds also in Quantum Probability Theory, where $ I_{probabilistic} $ is the \textbf{quantum probabilistic information}, namely \textbf{Von Neumann entropy}, ( X , Y ) denotes a state over a tensor product Von Neumann algebra $ A_{1} \bigotimes A_{2} $ having X and Y as marginal states, the equality holding iff ( X , Y ) is not entangled. The intuitive meaning of eq.\ref{eq:subadditivity of probabilistic information} (the information of a compound system is less or equal to the information of its parts) lead to think that such a condition should hold also for \textbf{classical algorithmic information}. As to \textbf{simple algorithmic entropy}, anyway, the subadditivity condition is violated by a disturbing logarithmic addendum causing that: \begin{theorem} \label{th:not subadditivity of simple algorithmic entropy} \end{theorem} NOT SUBADDITIVITY OF SIMPLE ALGORITHMIC ENTROPY \begin{equation} K ( ( \vec{x} , \vec{y} )) \; \not \stackrel{ + }{\leq} \; K( \vec{x}) \, + \, K(\vec{y}) \end{equation} The subadditivity property is instead satisfied by \textbf{prefix algorithmic entropy}: \begin{theorem} \label{th:subadditivity of prefix algorithmic entropy} \end{theorem} SUBADDITIVITY OF PREFIX ALGORITHMIC ENTROPY \begin{equation} I ( ( \vec{x} , \vec{y} )) \; \stackrel{ + }{\leq} \; I( \vec{x}) \, + \, I(\vec{y}) \end{equation} \item intuitive reasoning suggests that $ C_{M} - C_{ \Phi } $-algorithmic information should be \textbf{monotonic over prefixes}. Anyway one has that: \begin{theorem} \label{th:not monotonicity over prefixes of simple algorithmic entropy} \end{theorem} NOT MONOTONICITY OVER PREFIXES OF SIMPLE ALGORITHMIC INFORMATION \begin{equation} \vec{x} \, <_{p} \, \vec{y} \; \nRightarrow \; K ( \vec{x} ) \, \stackrel{ + }{\leq} \, K ( \vec{y} ) \end{equation} while: \begin{theorem} \label{th:monotonicity over prefixes of prefix algorithmic entropy} \end{theorem} MONOTONICITY OVER PREFIXES OF PREFIX ALGORITHMIC INFORMATION \begin{equation} \vec{x} \, <_{p} \, \vec{y} \; \Rightarrow \; I( \vec{x} ) \, \stackrel{ + }{\leq} \, I ( \vec{y} ) \end{equation} \item since the \textbf{probabilistic approach} and the \textbf{algorithmic approach} to $ C_{M} - C_{ \Phi } $ - Information Theory are different ways of formalizing the same object of investigation, it is natural to suppose that \textbf{$ C_{M} - C_{ \Phi } $-probabilistic information} and \textbf{$ C_{M} - C_{ \Phi } $-algorithmic information} are strictly connected notions. While the link is very clear in term of \textbf{prefix algorithmic entropy}, anyway, it is much obscure in terms of \textbf{simple algorithmic entropy}. To show this it is necessary to introduce some notion of $ C_{M} $ - Coding Theory: \begin{definition} \label{def:mathematically classical code} \end{definition} $ C_{M} $ - CODE: a partial function $ D : \Sigma^{\star} \stackrel{ \circ } { \mapsto } \Sigma^{\star} $ of decoding associating to each word $ \vec{x} $ belonging to the set HALTING(D) of \textbf{code words} its \textbf{source word} $ D(\vec{x})$. \medskip Given a $ C_{M} $ - code D and a source word $ \vec{x} \in \Sigma^{\star} $: \begin{definition} \end{definition} SET OF THE D - CODE WORDS OF $\vec{x}$: the (eventually empty) set $ D^{-1} (\vec{x})$. \medskip Let us observe that the definition\ref{def:mathematically classical code} doesn't require nor the surjectivity of a code (i.e. that each source word is codificable) neither the injectivity of a code (i.e. that each source word has only one code word). \medskip Let us now introduce a particular fundamental kind of code: \begin{definition} \end{definition} PREFIX-CODE: a code $ D : \Sigma^{\star} \stackrel{ \circ } { \mapsto } \Sigma^{\star} $ such that HALTING(D) is prefix-free \medskip The more fundamental property of prefix-codes is given by the following: \begin{theorem} \label{th:Kraft inequality} \end{theorem} KRAFT'S INEQUALITY \begin{hypothesis} \end{hypothesis} \begin{align*} I \text{ index set} & : cardinality(I) \leq \aleph_{0} \\ \{ l_{i} \in & {\mathbb{N}} \}_{i \in I} \end{align*} \begin{thesis} \end{thesis} \begin{equation} \exists \, D : \Sigma^{\star} \stackrel{ \circ } { \mapsto } \Sigma^{\star} \text{ prefix code} : \{ | \vec{x} | , \vec{x} \in HALTING(D) \} \, = \, \{ l_{i} \in {\mathbb{N}} \}_{i \in I} \; \Leftrightarrow \; \sum_{ i \in I} 2^{- l_{i}} \, \leq \, 1 \end{equation} We will appreciate the importance of Kraft Inequality as soon as we will introduce the \textbf{universal algorithmic probability} and the \textbf{Halting Probability}. \medskip Let us now start the probabilistic analysis of $ C_{M} $ - Coding Theory. Let us suppose that the generic source-word $ \vec{x} $ occur with probability $ P ( \vec{x} ) $. Given an injective prefix-code $ D : \Sigma^{\star} \stackrel{ \circ } { \mapsto } \Sigma^{\star} $ we can then introduce the: \begin{definition} \end{definition} AVERAGE CODE WORD LENGTH OF THE CODE D W.R.T. THE SOURCE CODE DISTRIBUTION P: \begin{equation} L_{D,P} \; := \; \sum_{\vec{x} \in HALTING(D)} P ( \vec{x} ) | D (\vec{x}) | \end{equation} It is clear that, in a communicational situation, the objective of a transmitter is to minimize the average code word length. Clearly a coding strategy will be the more clever the more it will assign short code words to highly probable source words and viceversa, in order to minimize the average code word length. \begin{definition} \end{definition} MINIMAL AVERAGE CODE WORD LENGTH ALLOWED BY THE DISTRIBUTION P: \begin{equation} L \; := \; \min \{ L_{D,P} \, , \, D \, prefix-code \} \end{equation} \begin{definition} \end{definition} OPTIMAL PREFIX-CODE W.R.T. THE SOURCE CODE DISTRIBUTION P: a prefix-code D such that: \begin{equation} L_{D,P} \; = \; L \end{equation} \smallskip The probabilistic approach to $ C_{M} - C_{\Phi} $ Information Theory is based on the following notion: \begin{definition} \label{def:Shannon entropy of a distribution} \end{definition} SHANNON ENTROPY OF THE DISTRIBUTION P: \begin{equation} H(P) \; := \; - \sum_{\vec{x} \in \Sigma^{\star}} P ( \vec{x} ) \log_{2} P ( \vec{x} ) \end{equation} The corner stone of $ C_{M} - C_{\Phi} $ Probabilistic Information Theory is the following: \begin{theorem} \label{th:mathematically classical mathematically physical noiseless coding theorem} \end{theorem} $ C_{M} - C_{\Phi} $ NOISELESS CODING THEOREM \begin{equation} H(P) \; \leq \; L \; \leq \; H(P)+1 \end{equation} \smallskip Let us now observe that \textbf{prefix algorithmic entropy} may be used to define a particular code: by definition we have that: \begin{equation} I( \vec{x} ) \, = \, | \vec{x}^{\star} | \end{equation} where $ \vec{x}^{\star} $ is the shortest input for the fixed universal Chaitin computer giving $ \vec{x} $ as output (or the first one in quasi-lexicographic order if there are many). The 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. \smallskip Since the code $ D_{I} $ is of pure algorithmic nature, 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 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 of H(P) stated by Theorem\ref{th:mathematically classical mathematically physical noiseless coding theorem} \smallskip But here the deep link between the \textbf{probabilistic-approach} and the \textbf{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 mathematically classical mathematically physical probabilistic information and mathematically classical mathematically physical algorithmic information} \end{theorem} LINK BETWEEN $C_{M}-C_{\Phi}$ PROBABILISTIC INFORMATION AND $C_{M}-C_{\Phi}$ ALGORITHMIC INFORMATION \begin{hypothesis} \end{hypothesis} P $ C_{M}-C_{\Phi} - \Delta_{0}^{0} $ 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} \smallskip Such a result of a substantial equivalence between \textbf{Shannon entropy} and \textbf{average algorithmic prefix entropy} has a strongly weaker counterpart in terms of \textbf{algorithmic simple entropy}. Indeed the two algorithmic entropies are linked by the following: \begin{theorem} \label{th:first Solovay theorem} \end{theorem} FIRST SOLOVAY'S THEOREM: \begin{align} I( \vec{x} ) \; & \; = \; K( \vec{x} ) \, + \, K( string^{- 1} ( K (\vec{x} )) \, + \, O ( K ( string^{- 1} K( string^{- 1} ( K (\vec{x} ))))) \\ K( \vec{x} ) \; & \; = \; I( \vec{x} ) \, - \, K( string^{- 1} ( K (\vec{x} )) \, - \, O ( I ( string^{- 1} I( string^{- 1} ( I (\vec{x} ))))) \end{align} that substituted in the Theorem\ref{th:link between mathematically classical mathematically physical probabilistic information and mathematically classical mathematically physical algorithmic information} gives: \begin{equation} - c_{P} \; \leq \; L_{D_{K},P} - H(P) \; \leq \; \sum_{\vec{x}} P ( \vec{x} ) K( string ^{-1} (C ( string ^{-1} ( \vec{x})))) \end{equation} which is bounded only if $ \sum_{\vec{x}} P ( \vec{x} ) K( string ^{-1} (C ( string ^{-1} ( \vec{x})))) $ converges. \item called U the fixed Chaitin universal computer let us introduce the main actors of some of the most fascinating developes of $ C_{M} - C_{\Phi} $ Algorithmic Information Theory: \begin{definition} \label{def:universal algorithmic probability} \end{definition} UNIVERSAL ALGORITHMIC PROBABILITY OF $ \vec{x} \in \Sigma^{\star} $: \begin{equation} P_{U} (\vec{x}) \; := \; \sum_{\vec{y} \in \Sigma^{\star} : U( \vec{y} ) = \vec{x} } 2^{- |\vec{y} | } \end{equation} \begin{definition} \label{def:halting probability} \end{definition} HALTING PROBABILITY: \begin{equation} \Omega_{U} \; := \; \sum_{ \vec{x} \in \Sigma^{\star}} P_{U} (\vec{x}) \end{equation} These notion has a very intuitive meaning: \begin{itemize} \item $ P_{U} (\vec{x}) $ is the probability that the computer U gives as output the string $ \vec{x} $ under an uniformely random distributed input. \item $ \Omega_{U} $ gives the probability that the computer U halts under an uniformely random distributed input. \end{itemize} Such a probabilistic meaning,anyway, lies on the fact that U is a \textbf{Chaitin computer} so that its halting set is prefix-free and hence Theorem\ref{th:Kraft inequality} implies that: \begin{equation} \label{eq:universal algorithmic probability takes values in the unitary interval} 0 \; \leq \; P_{U} (\vec{x}) \; \leq \; 1 \; \; \forall \vec{x} \in \Sigma^{\star} \end{equation} and that: \begin{equation} \label{eq:halting probability takes values in the unitary interval} 0 \; \leq \; \Omega_{U} \; \leq \; 1 \end{equation} If we considered \textbf{simple algorithmic information} instead of \textbf{prefix algorithmic information} and hence we adopted a \textbf{non Chaitin computer}, anyway, the halting set of U wouldn't be prefix-free anymore, so that Theorem\ref{th:Kraft inequality} wouldn't imply eq.\ref{eq:universal algorithmic probability takes values in the unitary interval} and eq.\ref{eq:halting probability takes values in the unitary interval}. \item Unlike \textbf{prefix algorithmic information}, \textbf{simple algorithmic information} is affected by oscillations that exclude the possibility of using it to define the notion of algorithmic randomness for sequences in an enough robust way as we will show in the next section \end{enumerate} \newpage \section{Chaitin random strings and sequences of cbits} Let us suppose to make 100 independent tosses of a coin. If we obtained head all times we would certainly claim the the used coin is not fair. But let us observe that, assuming that the coin is fair, the string of 100 heads have the same exact probability, i.e. $ 2^{- 100} $, of any other binary string of 100 cbits. So, which foundation could we give at our claim that the coin is not fair? The first to analyze this problem was Laplace that dedicated to this issue the Fifth Principle among the \textit{"General Principles of the calculus of probabilities"} making the content of the third chapter of his pioneering work \cite{Laplace-51}; it is worth to report his own words: \begin{center} \textit{"Sixth Principle: Each of the causes to which an observed event may be attributed is indicated with just as much likelihood as there is probability that the event will take place supposing the event to be constant. The probability of the existence of any one of these causes is then a fraction whose numerator is the probability of the event resulting from this cause and whose denominator is the sum of the similar probabilities relative to all the causes; if these various causes considerated \`{a} priori, are unequally probable, it is necessary in place of the probability of the event resulting from each cause, to employ the product of this probability by the possibility of the cause itself. This is the fundamental principle of this branch of the analysis of chances which consists in passing from events to causes.} \textit{This principle gives the reason why we attribute regular events to a particular cause. Some philosophers have thought that these events are less possible than others and that at the play of heads and tails, for example, the combiantion in which heads occurs twenty successive times is less easy in its nature than those where head and tails are mixed in irregular manner. But this opinion suppose that past events have an influence on the possibility of future events which is not at all admissible. The regular combinations occur more rarely only because they are less numerous. $ \cdots $} \textit{Thus at the play of head and tail the occurence of heads a hundred successive times appears to us extraordinary because of the almost infinite number of combinations which may occur in a hundred throws; and if divide the combinations in two regular series containing an order easy to comprehend, and into irregular series, the latter are incomparably more numerous"} \end{center} Laplace catchs the following basic points: \begin{itemize} \item what the string made of one hundred heads have of particular is to possess some kind of regularity \item this string has the same probability $ 2^{- 100} $ of every other string \item the fact that if this string of results occurs we can claim the coin was unfair is founded by the observation that the fraction of the set of 100 cbit strings made by strings having some kind of regularity, i.e. the probability that a string of this kind occurs, is enormously low and , conseguentially, the probability that a string of this kind occurs is extraordinarily low. \end{itemize} The only thing Laplace wasn't able to explain, as anyone else for little less than two centuries, was the exact meaning of the locution \emph{\textbf{"to possess some regularity"}}. In this dissertation we will see how Classical Algorithmic Information Theory gives many equilavent mathematical characterization of this \textbf{absence of regularity} or, as we say it nowadays , of this \textbf{algorithmic randomness}. Among these characterization the more important one is with no doubt that as \textbf{algorithmic incompressibility}. As an \textbf{algorithmically incompressible} object we mean, informally speaking , an object whose more concise algorithmic description is substantially its own assignation. So one could be to tempted to say that the string $ \vec{x} \in \Sigma^{\star} $ is algorithmically random iff: \begin{equation} \label{eq:naife simple algorithmic random string} K( \vec{x} ) \; = \; | \vec{x} | \end{equation} or iff: \begin{equation} \label{eq:naife prefix algorithmic random string} I( \vec{x} ) \; = \; | \vec{x} | \end{equation} The meaningness of these definitions, anyway, appear evident as soon as one keeps into account , as to eq.\ref{eq:naife simple algorithmic random string}, the issue of the additive constant involved in the passage from a \textbf{universal computer} to another \textbf{universal computer} and, as to eq.\ref{eq:naife prefix algorithmic random string}, the issue of the additive constant involved in the passage from a \textbf{Chaitin universal computer} to another \textbf{Chaitin universal computer}. The notion of random string originally introduced by Kolmogorov in 1965 was the following: given a constant $ c \in {\mathbb{R}}_{+} $: \begin{definition} \label{def:Kolmogorov c-random string} \end{definition} $ \vec{x} \in \Sigma^{\star} $ IS c-KOLMOGOROV-RANDOM: \begin{equation} K( \vec{x} ) \; \geq \; | \vec{x} | \, - \, c \end{equation} \smallskip Before of analyzing the analogous notion involving \textbf{prefix algorithmic information} instead of \textbf{simple algorithmic information} let us introduce the following preliminary notion: \begin{definition} \label{def:busy beaver function} \end{definition} BUSY BEAVER FUNCTION: the function $ \Sigma : {\mathbb{N}} \, \rightarrow \, {\mathbb{N}} $: \begin{equation} \Sigma(n) \; := \; \max_{ \vec{x} \in \Sigma^{n}} I( \vec{x} ) \end{equation} It obeys the following \cite{Calude-94}: \begin{theorem} \end{theorem} \begin{equation} \Sigma(n) \; \stackrel{ + }{=} \; n \, + \, I ( string(n)) \end{equation} \smallskip Chaitin's idea was that of defining the random strings of length n to be the strings with maximal prefix entropy among the strings of length n. So, given a natural number m: \begin{definition} \label{def:Chaitin m-random string} \end{definition} $ \vec{x} \in \Sigma^{\star} $ IS CHAITIN m-RANDOM: \begin{equation} I( \vec{x} ) \; \geq \; \Sigma( | \vec{x} | ) \, - \, m \end{equation} We will denote the set of al the Chaitin m-random binary strings by $CHAITIN-m-RANDOM( \Sigma^{\star}$. a 0-Chatin random string is often called simply a \textbf{Chaitin random}. Following this terminology we will pone: \begin{equation} CHAITIN-RANDOM( \Sigma^{\star}) \; := \; CHAITIN-0-RANDOM( \Sigma^{\star}) \end{equation} \smallskip \begin{remark} \label{rem:impossibility of a sharp distinction between regularity and randomness for strings} \end{remark} IMPOSSIBILITY OF A SHARP DISTINCTION BETWEEN REGULARITY AND RANDOMNESS FOR STRINGS It is essential to observe that the introduction of additive constants in both definition\ref{def:Kolmogorov c-random string} and definition\ref{def:Chaitin m-random string} solves the problem of the inconsistence of, respectively, definition\ref{eq:naife simple algorithmic random string} and definition\ref{eq:naife prefix algorithmic random string} only in a partial way: indeed definition\ref{def:Kolmogorov c-random string} and definition\ref{def:Chaitin m-random string} continue to depend upon, respectively, the fixed \textbf{universal computer} and the fixed \textbf{universal Chaitin computer}. The improvement is that under these ansatzs one doesn't lose algorithmic randomness of strings but passes simply from algorithmic randomness relative to a certain constant to algorithmic randomness relative to a different constant. But in this way one has to look at the transition from regular to random strings as a continuous, asymptotic one: indeed the effective connotation of randomness given by the specification that a certain string $ \vec{x}\in \Sigma^{\star} $ is m-Chaitin random is the more significative the more high is the difference $ | \vec{x} | - m $. A sharp distinction is possible only for sequences. In chapter\ref{chap:Classical algorithmic randomness as stability of the relative frequences under proper classical algorithmic place selection rules} we will give a clear, intuitive explanation of this fact in terms of Classical Gambling Theory. Unfortunately, as we will show in part\ref{part:The road for quantum algorithmic randomness}, this point hasn't received the necessary consideration in most the attempts of defining quantum algorithmic randomness, that , erroneously to our opinion, concentrate the analysis to strings of qubits considering this case as simpler and only later, in a derivate mode, pass to analyze sequences of qubit. We anticipate here that our point of view is opposite: since exactly as in the classical case a sharp distinction between regularity and randomness is possible only for sequences of qubits, the analysis of quantum algorithmic randomness has to start from sequences of qubit. \bigskip Let us now observe that there exist many reasons to prefer Chaitin-randomness to Kolmogorov-randomness: \begin{enumerate} \item the adoption of Chaitin randomness allows to give a clear quantitative foundation to the observation Laplace himself realized almost two centuries ago, namely that the strings not having any kind of regularity, the patternless ones, are the overwhelming majority: \begin{theorem} \end{theorem} \begin{equation} \exists c \in {\mathbb{R}}_{+} \; : \; cardinality ( CHAITIN-RANDOM( \Sigma^{n})) \, > \, 2^{n - c} \; \; \forall n \in {\mathbb{N}} \end{equation} \item Robert Solovay has proved that Chaitin randomness is stronger than Kolmogorov randomness \item Chaitin randomness may be easily extended to binary sequences defining, informally speaking, an algorithmic random sequence as one whose prefixes are all Chaitin algorithmic random. As we will now show, the \textbf{phenomenon of the oscillations of simple algorithmic entropy} avoid this possibility for Kolmogorov randomness. \end{enumerate} \medskip Let us introduce , first of all, a useful notation. Given a sequence $ \bar{x} \in \Sigma^{\infty} $ let us denote by $ x_{n} $ its $ n^{th} $ digit, by $ \vec{x}(n) $ its prefix of length n and by $ \vec{x}(n , m) $ ($ n \leq m$) the substring of $ \bar{x} $ obtained taking its digits from the $ n^{th} $ to the $ m^{th} $, namely: \begin{equation} \vec{x}(n , m) \; := \; x_{n} \cdots x_{m} \, \in \, \Sigma^{m-n} \end{equation} Let us then observe that by identifying the generic string $ \vec{x} \in \Sigma^{\infty} $ with the sequence $ \vec{x} 0^{\infty} \in $ we can look at $ \Sigma^{\star} $ as a proper subset of $ \Sigma^{\infty} $. Let us then introduce the following useful map: \begin{definition} \label{def:numeric representation} \end{definition} NUMERIC REPRESENTATION: $ {\mathcal{N}} : \Sigma^{\infty} \, \mapsto \, [ 0 ,1) $: \begin{equation} {\mathcal{N}} ( \bar{x} ) \; := \; \sum_{n = 1}^{\infty} \frac{x_{n}}{2^{n}} \end{equation} whose restriction $ {\mathcal{N}} |_{ \Sigma^{\infty} - \Sigma^{\star}} $ is a bijection and allows, conseguentially, to identify $ \Sigma^{\infty} $ with the set $ [ 0 ,1 ) $. Let us then introduce the probability measure: \begin{definition} \end{definition} UNBIASED PROBABILITY MEASURE ON $ \Sigma^{\infty} $: $ P_{unbiased} \, : \, 2^{ \Sigma^{\infty}} \; \stackrel{\circ }{\rightarrow} \; [0,1]$ : \begin{align} HALTING(P_{unbiased}) \; & = \; {\mathcal{F}}_{cylinder} \\ P_{unbiased} ( \Gamma_{\vec{x}} ) \; & \equiv \; \frac{1}{2^{| \vec{x} |}} \; \; \forall \, \vec{x} \, \in \, \Sigma^{\star} \end{align} where: \begin{definition} \end{definition} CYLINDER SET W.R.T. $ \vec{x} \, = ( x_{1} , \ldots , x_{n} ) \, \in \, \Sigma^{\star} $: \begin{equation} \label{eq:cylinder set} \Gamma_{\vec{x}} \; \equiv \; \{ \bar{y} = ( y_{1} , y_{2} , \ldots ) \in \Sigma^{\infty} \; : \; y_{1} = x_{1} , \ldots , y_{n} = x_{n} \} \end{equation} \begin{definition} \end{definition} CYLINDER - $ \sigma $ - ALGEBRA ON $ \Sigma^{\infty} $: \begin{equation} {\mathcal{F}}_{cylinder} \; \equiv \; \sigma- \text{algebra generated by} \{ \Gamma_{\vec{x}} \, : \, \vec{x} \in \Sigma^{\star} \} \end{equation} \smallskip In the numeric representation of $ \Sigma^{\infty} $ as the real interval $ [ 0 ,1) $, $P_{unbiased} $ is, clearly, nothing but Lebesgue measure \cite{Lebesgue-73}. Denoted by $ N_{i}^{n} ( \bar{x} ) $ the number of successive $ i \in \Sigma $ ending in position n of the sequence $ \bar{x} $ the First Borel-Cantelli's Lemma implies that (cfr. the fifth section of the fourth chapter of \cite{Billingsley-95}): \begin{theorem} \label{th:on the islands of regularity of almost all sequences} \end{theorem} \begin{align} P_{unbiased} & ( \{ \bar{x} \in \Sigma^{\infty} \, : \, \limsup_{ n \rightarrow \infty} N_{0}^{n} ( \bar{x} ) \, = \, 1 \} ) \; = \; 1 \\ P_{unbiased} & ( \{ \bar{x} \in \Sigma^{\infty} \, : \, \limsup_{ n \rightarrow \infty} N_{1}^{n} ( \bar{x} ) \, = \, 1 \} ) \; = \; 1 \end{align} \smallskip Theorem\ref{th:on the islands of regularity of almost all sequences} tells us that for $ P_{unbiased} $-almost all sequences $ \bar{x} \in \Sigma^{\infty} $ there exist infinitely many n for which: \begin{equation} \vec{x}(n) \; \stackrel{ + }{=} \; \vec{x} ( 1 , n - \log_{2} n) 0^{n} \end{equation} i.e.: \begin{equation} \label{eq:oscillations of simple algorithmic entropy} K( \vec{x}(n) ) \stackrel{ + }{=} \; n - \log_{2} n \end{equation} This suggest that if we adopted the following definition of algorithmic randomness for sequences: \begin{definition} \label{def:Kolmogorov random sequence} \end{definition} $ \bar{x} \in \Sigma^{\infty} $ IS KOLMOGOROV RANDOM: \begin{equation} \exists c \in {\mathbb{R}}_{+} \; : \; K ( \vec{x}(n) ) \, > \, n - c \; \; \forall n \in {\mathbb{N}} \end{equation} there wouldn't exist Kolmogorov random sequences. That this is indeed the case may be rigorously proved observing that the existence of infinitely many n such that eq.\ref{eq:oscillations of simple algorithmic entropy} holds may be proved to hold for all sequences (not only with $ P_{unbiased}$- probability one). \smallskip This doesn't happen if we use prefix algorithmic entropy. \begin{definition} \label{def:Chaitin random sequence} \end{definition} $ \bar{x} \in \Sigma^{\infty} $ IS CHAITIN RANDOM: \begin{equation} \exists c \in {\mathbb{R}}_{+} \; : \; I ( \vec{x}(n) ) \, > \, n - c \; \; \forall n \in {\mathbb{N}} \end{equation} We will denote the set of all the Chaitin random sequences by $ CHAITIN -RANDOM(\Sigma^{\infty})$. By the numeric representation's map the notion of Chaitin randomness may be immediately extended to reals numbers in the following way: \begin{definition} \label{def:Chaitin random real number} \end{definition} $ x \in [ 0 \, , \, 1 ) $ IS CHAITIN RANDOM: \begin{equation} ({\mathcal{N}} | _{\Sigma^{\infty} \, - \, \Sigma^{\star}})^{- 1} (\Omega) \end{equation} We will denote the set of all the random real numbers by $ CHAITIN -RANDOM( [ 0 , 1 )) $ As we will prove later, \textit{"almost all"} the numbers in the unitary interval are Chaitin-random. In particular one has the following: \begin{theorem} \label{th:Chaitin randomness of the halting probability} \end{theorem} CHAITIN RANDOMNESS OF THE HALTING PROBABILITY: \begin{equation} \Omega \; \in \; CHAITIN-RANDOM( [ 0 , 1 )) \end{equation} Supposing now to let the fixed Chaitin universal computer to vary, Theodore A. Slaman has recentely proved the followin remarkable \cite{Kucera-Slaman-01}: \begin{theorem} \label{th:Slaman's theorem} \end{theorem} SLAMAN'S THEOREM: \begin{equation} \{ \, \Omega_{U} \, , \, : \, U \text{ Chaitin's universal computer } \, \} \; = \; CHAITIN-RANDOM( [ 0 \, , \, 1 ) ) \, \bigcap \, REC-EN( {\mathbb{R}}) \end{equation} \newpage \section{Brudno random sequences of cbits} \label{sec:Brudno random sequences of cbits} As to the definition of algorithmically random binary sequences we have seen in the previous section that the phenomenon of oscillations of simple algorithmic entropy causes that, denoted by $KOLMOGOROV-RANDOM(\Sigma^{\infty})$ the set of all the Kolmogorov-random binary sequence, one has that: \begin{theorem} \label{th:not existence o Kolmogorov random sequences} \end{theorem} NOT EXISTENCE OF KOLMOGOROV RANDOM SEQUENCES: \begin{equation} KOLMOGOROV-RANDOM( \Sigma^{\infty} ) \; = \; \emptyset \end{equation} \smallskip One could , at this point, argue that the existence of infinite islands of regularity in a generic sequence resulting in the logarithmic deficit of simple algorithmic entropy showed by an infinite number of its prefixes is a false problem since what is really relevant is the rate of plain algorithmic entropy for digit of the prefixes, i.e. the ratio $ \frac{K( \vec{x}(n)) }{n} $ for whose asymptotic behaviour the logarithmic deficits are irrilevant since obviuosly: \begin{equation} \lim_{n \rightarrow \infty} \frac{ \log_{2}(n) }{n} \; = \; 0 \end{equation} This way of reasoning led A.A. Brudno to introduce the following notions: \begin{definition} \label{def:Brudno algorithmic entropy 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 prefix entropy instead of simple entropy would result in a different definition of the algorithmic entropy of a sequence. That this is not the case is the claim 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} ) \; = \; 1 \end{equation} We will denote the set of all the Brudno random binary sequences by $ BRUDNO( \Sigma^{\infty}) $. \smallskip Anyway one is here faced to a problem almost always misunderstood that is the main source of a sort of incomunicability between the scientific community of mathematical physicists studying Dynamical Systems Theory and the scientific community of the logico-mathematicians and Theoretical-Computer scientists studying Algorithmic Information Theory: \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} \smallskip Such a theorem was proven by Brudno himself in the last section of \cite{Brudno-83} by the explicit presentation of a Brudno-random sequence doesn't passing a Martin-L\"{o}f test. We postpone the presentation of such a proof to section\ref{sec:Equivalence between passage of a Martin Lof universal statistical test and Chaitin randomness} where the involved properties of universal sequential Martin-L\"{o}f test are introduced. \newpage \section{Brudno algorithmic entropy versus the Uspensky abstract approach} \label{sec:Brudno algorithmic entropy versus the Uspensky abstract approach} In this section we will show that definition\ref{def:Brudno algorithmic entropy of a sequence} is not compatible with Uspensky's abstract approach of defining algorithmic information discussed in section\ref{sec:Uspensky's abstract definition of algorithmic information}. Uspensky's abstract approach would, indeed, require the specification of: \begin{enumerate} \item a \textbf{concordance relation} $ {\mathcal{R}} $ \item a \textbf{point measure} $ \mu $ \end{enumerate} on $ \Sigma^{\infty} $ such to constitute a \textbf{metric aggregate} $ ( \Sigma^{\infty} \, , \, {\mathcal{R}} \, , \, \mu )$. Both these points are highly not-trivial. Remembering remark\ref{rem:context dependence of the computability constraint} we have to keep attention on the meaning of the computability constraint. Indeed, by theorem\ref{th:cardinalities of strings and sequences}, we see that the definition of the concordance relation $ {\mathcal{R}} $ exit from the boundaries of $ C_{M}$-Classical Recursion Theory. As we have anticipated in section\ref{sec:The distinction between mathematical-classicality and physical-classicality}, just as to Computability Theory by \textbf{physically classical computers} of (partial) functions on sets $ S \, : \, card(S) \, = \, \aleph_{1}$ many different inequivalent candidate theories have been proposed: \begin{enumerate} \item the Orthodox Theory generated by the studies of Grzegorczyck - Lacombe \cite{Pour-El-Richards-89} \item the theory developed by the so called Markov School in the framework of Constructive Mathematics \cite{Odifreddi-89} \item the Blum - Shub - Smale 's Theory \cite{Smale-92}, \cite{Blum-Cucker-Shub-Smale-98} \end{enumerate} The basic notion of the Othodox Theory, namely the definition of a \textbf{recursive real number}, seems rather robust: starting from the $ C_{\Phi} $-Computability of the whole $ {\mathbb{Q}} $ the strategy of defining a \textbf{recursive real number} consists in effectivizing a method for constructing $ {\mathbb{R}} $ from $ {\mathbb{Z}} $; as shown by R.M. Robinson whichever of these methods one effective: \begin{enumerate} \item the construction of $ {\mathbb{R}} $ from $ {\mathbb{Z}} $ through Cauchy sequences \item the construction of $ {\mathbb{R}} $ from $ {\mathbb{Z}}$ through nested intervals \item the construction of $ {\mathbb{R}} $ from $ {\mathbb{Z}}$ through the Dedekind Cut \item the construction of $ {\mathbb{R}} $ from $ {\mathbb{Z}}$ through the expansion to base b, where b is an integer $ > 1 $. \end{enumerate} one results in the the same set $ REC ({\mathbb{R}}) $ \cite{Pour-El-Richards-89}, \cite{Pour-El-99}. Let us review the first of these strategies: given a sequence $ \{ r_{n} \}_{ n \in {\mathbb{N}}} $ of rational numbers: \begin{definition} \end{definition} $ \{ r_{n} \} $ IS RECURSIVE: \begin{equation} \exists b , c , s \in C_{M} - C_{\Phi} - \Delta_{0}^{0}-map({\mathbb{N}},{\mathbb{N}}) \; : \; r_{n} \, = \, (- 1) ^{s(n)} \frac{ b(n) }{ c(n) } \end{equation} \begin{definition} \end{definition} $ \{ r_{n} \} $ CONVERGES EFFECTIVELY TO $ x \in {\mathbb{R}} $: \begin{equation} \exists e \in C_{M} - C_{\Phi} - \Delta_{0}^{0}-map({\mathbb{N}},{\mathbb{N}}) \; : \; m \geq e(n) \, \Rightarrow \, | r_{m} - x | < \frac{1}{2^{n}} \end{equation} \smallskip Given a real number $ x \in {\mathbb{R}} $: \begin{definition} \label{def:r.e. real numbers} \end{definition} RECURSIVELY ENUMERABLE REAL NUMBERS: \begin{multline} REC-EN( {\mathbb{R}} ) \; := \; \{ x \in {\mathbb{R}} ) \, : \\ \text{ there is a increasing, computable sequence of rationals which converges to x} \} \end{multline} \begin{definition} \label{def:recursive real number} \end{definition} RECURSIVE REAL NUMBERS: \begin{multline} REC( {\mathbb{R}} ) \; := \; \{ x \in {\mathbb{R}} ) \, : \\ \text{ there is a computable sequence of rationals which converges effectively to x } \} \end{multline} \smallskip Given a complex number $ z \in {\mathbb{C}} $: \begin{definition} \label{def:recursive complex number} \end{definition} z IS RECURSIVE: \begin{equation} \Re(z) \in REC( {\mathbb{R}} ) \; and \; \Im(z) \in REC( {\mathbb{R}} ) \end{equation} \smallskip We will denote the set of all the recursive complex numbers by $ REC ( {\mathbb{R}} ) $. It may be proved that: \begin{theorem} \end{theorem} BASIC PROPERTIES OF $ REC( {\mathbb{R}} ) $ \begin{enumerate} \item $ REC ( {\mathbb{R}} ) $ is a \textbf{closed field} \item \begin{equation} cardinality( REC ( {\mathbb{R}} ) ) \; = \; \aleph_{0} \end{equation} \end{enumerate} Obviously this immediately implies that: \begin{corollary} \label{cor:enumerability of the set of all the recursive complex numbers} \end{corollary} \begin{equation} cardinality( REC ( {\mathbb{C}} )) \; = \; \aleph_{0} \end{equation} \medskip To understand in which sense Corollary\ref{cor:enumerability of the set of all the recursive complex numbers} may be seen highly unsatisfactory and even suggest the necessity of an Eterodox Theory, let us start from the analysis Roger Penrose dedicates to the issue: \begin{center} \textbf{Is Mandelbrot's set recursive?} \end{center} in the seventh section of the fourth chapter of his book \cite{Penrose-89} and its reformulation by Lenore Blum, Felipe Cucker, Michael Shub and Steve Smale in the first two chapters of their book \cite{Blum-Cucker-Shub-Smale-98} significatively reporting a picture of Mandelbrot's set on its front cover. Given a generic complex number $ c \in {\mathbb{C}} $ let us introduce the polynomial $ p_{c} (z) \; := \; z^{2} + c $ and let us denote by $ p_{c}^{(n)} (z) $ its $ n^{th} $ iterate. \begin{definition} \label{def:Mandelbrot set} \end{definition} MANDELBROT'S SET: \begin{equation} {\mathcal{M}} \; := \; {\mathbb{C}} \, - \, \{ c \in {\mathbb{C}} \, : \, \lim_{n \rightarrow \infty } p_{c}^{(n)} (0) = \infty \} \end{equation} A key property of Mandelbrot's set is stated by the following \cite{Falconer-90}: \begin{theorem} \end{theorem} $ {\mathcal{M}} $ is the halting set of the following algorithm: \begin{center} Label[start] Input c $ x^{2} + c \; \rightarrow \; x $ If $ | x | \, \leq \, 2 $ then Goto start Output 1 Halt \end{center} To answer Penrose's query one needs an algorithm that, given the input $ c \in {\mathbb{C}} $, will decide in a finite number of steps whether or not $ c \in {\mathcal{M}} $. Penrose appeals to the Orthodox Theory, but immediately refutes it: \begin{center} \textit{"One implication of this is that even with such a simple set as the unit disc $ \cdots $ there would be no algorithm for deciding for sure $ \cdots $ whether the computable number $ x^{2} + y^{2} $ is actually equal to 1 or not, this being the criterion for deciding whether or not the computable complex number $ x + i y $ lies on the unit circle $ \cdots $ Clearly that is not what we want"} \end{center} Then he tries to follow other approaches but at the end he concludes that: \begin{center} \textit{"One is left with the strong feeling that the correct viewpoint has not yet been arrived at"} \end{center} Blum, Cucker, Shub and Smale settle Penrose's question in the framework of their foundation of Computability Theory over a generic ring \cite{Smale-92} as a generalization of the Goldstine - Von Neumann axiomatization of Flowchart Theory (cfr. par.1.5 of \cite{Odifreddi-89}). Introduced the following notion: \begin{definition} \end{definition} $ S \; \subset \; {\mathbb{C}} $ IS A SEMI-ALGEBRAIC SET: it is a Boolean combination of sets defined by polynomial equalities and disequalities \smallskip Then they prove that a necessary condition for the decidability of a set $ S \; \subset \; {\mathbb{C}} $ w.r.t. Computation Theory over the ring $ {\mathbb{R}} $ is that it is the countable union of semi-algebraic sets over $ {\mathbb{R}} $. That this is not the case for the Mandelbrot's set follows by Shishikura's Theorem stating that the boundary of $ {\mathcal{M}} $ has Hausdorff dimension two, resulting in the following: \begin{theorem} \label{th:Blum Cucker Shub Smale incomputability of Mandelbrot set} \end{theorem} $ {\mathcal{M}} $ is not Blum, Cucker, Shub and Smale computable \medskip Following Uspensky abstract approach of defining algorithmic information, one would infer from Theorem\ref{th:Blum Cucker Shub Smale incomputability of Mandelbrot set} that $ {\mathcal{M}} $ has infinite algorithmic information, constrasting which what is claimed by another book reporting a picture of (part of) the Mandelbrot's set on its front cover, namely \cite{Cover-Thomas-91}, and stating that its information content is essentially zero. That the applicability of the Uspensky abstract approach to this particular case might be problematic, anyway, results by the obsevation that it doesn't seem to exist some natural \textbf{point measure} to use in the the specification of the \textbf{metric aggregate} $ ( \Sigma^{\infty} \, , \, {\mathcal{R}} \, , \, \mu )$. This throws a shadow on the same foundation of $ NC_{M} - C_{\Phi} $ - Algorithmic Information that is, as has been recentely remarked by Chaitin in the first paragraph of the fourth chapter of \cite{Chaitin-01}, mostly an unexplored field. Chaitin discusses this subject in the usual concretelly LISP programming attitude he followed in his other two Springer books \cite{Chaitin-98}, \cite{Chaitin-99}, adding to his version of LISP a new primitive function \textbf{display} that allow to get the partial outputs of a non-halting computation, and hence considering the algorithmic information of (so produced) infinite sets of S-expressions: in this way he concretely shows that the infinite version of $ C_{\Phi} $ - Algorithmic Information Theory differs for the finite version in many respects, an example being the violation of Theorem\ref{th:subadditivity of prefix algorithmic entropy}. \newpage \section{The algorithmic approach to Classical Chaos Theory and Brudno's Theorem} Let us review the basic notions 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} \smallskip \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 ) $ \smallskip \begin{definition} \label{def:classical dynamical system} \end{definition} CLASSICAL DYNAMICAL SYSTEM: a therne $ ( 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} \medskip 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} \medskip \begin{example} \end{example} CLASSICAL SHIFTS \begin{definition} \label{def:def:classical shift} \end{definition} CLASSICAL SHIFT OVER $ \Sigma $: a classical dynamical system $ ( \, \Sigma^{\infty} \, , \, \sigma \, , \, \mu ) $ such that: \begin{equation} \begin{split} \sigma & : \Sigma^{\infty} \rightarrow \Sigma^{\infty} \\ ( \sigma & \bar{x} ) _{n} \; := \; x_{n+1} \end{split} \end{equation} and: \begin{equation} HALTING( \mu ) \; = \; {\mathcal{F}}_{cylinder} \end{equation} \begin{remark} \label{rem:classical shift is synonimous of discrete-time stationary classical stochastic process} \end{remark} CLASSICAL SHIFT IS SYNONIMOUS OF DISCRETE-TIME STATIONARY CLASSICAL STOCHASTIC PROCESS The notion of a classical shift is nothing but a way of inglobing the Theory of Classical Stationary Stochastic Processes as a sub-discipline of Classical Ergodic Theory. As we will see in section\ref{sec:From the communicational-compression of the Quantum Coding Theorems to the algorithmic-compression in Quantum Computation} an analogous inglobation is possible in a quantum case. That the notion of a classical shift over $ \Sigma $ is indeed equivalent to the notion of a classical stationary stochastic process over $ \Sigma $ follows immediately by the following two facts: \begin{enumerate} \item every classical probability measure $ \mu $ on $ \Sigma^{\infty} $ such that $ HALTING( \mu ) \; = \; {\mathcal{F}}_{cylinder} $ individuates the classical stationary stochastic process over $ \Sigma $ with \textbf{occurence probability of strings}: \begin{equation} \label{eq:occurence probability of strings} p_{k} ( i_{1} , \cdots , i_{k} ) \; \equiv \; \mu ( \Gamma_{( i_{1} , \cdots , i_{k} )}) \; \; i_{1} , \cdots \ i_{k} \, \in \Sigma , k \in { \mathbb{N}} \end{equation} satisfying the conditions: \begin{equation} \label{eq:first constraint on the occurence probability of strings} p_{k} ( i_{1} \, , \, \cdots \, i_{k} \, ) \; \geq \; 0 \end{equation} \begin{equation} \label{eq:second constraint on the occurence probability of strings} \sum_{i \in \Sigma} p_{k+1} ( i_{1} \, , \, \cdots \, i_{k} \, i ) \; = \; p_{k} ( i_{1} \, , \, \cdots \, i_{k} \, ) \end{equation} \begin{equation} \label{eq:third constraint on the occurence probability of strings} \sum_{i \in \Sigma } p_{1} ( \, i \, ) \; = \; 1 \end{equation} \item the collection of functions: \begin{equation*} p_{k} ( i_{1} \, , \, \cdots \, i_{k} \, ) \; \; i_{1} \, , \, \cdots \, i_{k} \, \in \Sigma \, , \, k \in {\mathbb{N}} \end{equation*} expressing the \textbf{occurence probability of strings} of a classical stationary stochastic process (and, hence, satisfying the constraints eq.\ref{eq:first constraint on the occurence probability of strings}, eq.\ref{eq:second constraint on the occurence probability of strings}, eq.\ref{eq:third constraint on the occurence probability of strings}) individuates the $ \sigma$-invariant classical probability measure $ \mu $ on $ \Sigma^{\infty} $ such that $ HALTING( \mu ) \; = \; {\mathcal{F}}_{cylinder} $ and: \begin{equation} p_{k} ( i_{1} , \cdots , i_{k} ) \; = \; \mu ( \Gamma_{( i_{1} , \cdots , i_{k} )}) \; \; i_{1} , \cdots \ i_{k} \, \in \Sigma , k \in { \mathbb{N}} \end{equation} \end{enumerate} \smallskip Let us introduce some useful notion: \begin{definition} \label{def:stochastic vector} \end{definition} STOCHASTIC VECTOR OVER $ \Sigma $: $ \vec{P} \; = \; \begin{pmatrix} p_{0} \\ p_{1} \end{pmatrix}$ such that: \begin{align} p_{i} & \geq 0 \; \; i=0,1 \\ \sum_{i \in \Sigma } & p_{i} \; = \; 1 \end{align} i.e. a column vector specifying a probability distribution over $ \Sigma $. \smallskip \begin{definition} \label{def:stochastic matrix} \end{definition} STOCHASTIC MATRIX OVER $ \Sigma $: $ 2 \, \times \, 2 $ matrix: $ \hat{P} = \begin{pmatrix} p_{0,0} & p_{0 , 1 } \\ p_{1,0} & p_{1,1} \end{pmatrix} $ such that: \begin{align} p_{i,j} & \geq 0 \; \; i,j=0,1 \\ \sum_{j \in \Sigma} & p_{i,j} \; = \; 1 \; \; i=0,1 \end{align} \smallskip We can now introduce some basic classical shift: \begin{definition} \label{def:classical bernoulli shift} \end{definition} CLASSICAL BERNOULLI SHIFT OVER $ \Sigma $ W.R.T. THE STOCHASTIC VECTOR $ \vec{P} \; = \; \begin{pmatrix} p_{0} \\ p_{1} \end{pmatrix}$: the classical shift over $ \Sigma $ with measure $ \mu $ : \begin{equation} p_{k} ( \, i_{1} \, , \, \cdots \, i_{k} \, ) \; = \; \prod_{l=1}^{k} p ( \, i_{l} \, ) \; \; \forall k \in {\mathbb{N} } \end{equation} \smallskip Given a stochastic vector $ \vec{e} \; := \; \begin{pmatrix} e_{0} \\ e_{1} \end{pmatrix}$ and a stochastic matrix $ \hat{P} \; := \begin{pmatrix} p_{00} & p_{01} \\ p_{10} & p_{11} \end{pmatrix}$ such that: \begin{equation} ( \vec{P} )^{T} \hat{P} \; = \; \hat{P} \end{equation} \begin{definition} \label{def:classical markov shift} \end{definition} CLASSICAL MARKOV SHIFT OVER $ \Sigma $ W.R.T. THE STOCHASTIC VECTOR $ \vec{e} $ AND THE STOCHASTIC MATRIX $ \hat{P} $ the classical shift over $ \Sigma $ with measure $ \mu $ : \begin{equation} p_{k} ( i_{1} \, , \, \cdots \, i_{k} ) \; = \; e_{i_{1}} \, p_{i_{1} , i_{2}} \, \cdots \, p_{i_{k-1} , i_{k}} \end{equation} \smallskip \begin{remark} \label{rem:classical shift is synonimous of stationary classical information source} \end{remark} CLASSICAL SHIFT IS SYNONIMOUS OF STATIONARY CLASSICAL INFORMATION SOURCE We have seen in remark\ref{rem:classical shift is synonimous of discrete-time stationary classical stochastic process} that the notion of classical shift over $ \Sigma $ is equivalent to the notion of a stationary classical stochastic process over $ \Sigma $. But a classical stochastic process $ \{ x_{n} \} $ may be equivalentely seen as a classical information source, considering the random variable $ x_{n} $ as the letter trasmitted at time n by a sender (Alice) to a receiver (Bob) through a proper communicational channel. The resulting equivalence between the notion of a classical shift and the notion of a stationary classical information source persists at the quantum level as we will see in the section\ref{sec:The algorithmic approach to Quantum Chaos Theory: quantum algorithmic information versus quantum dynamical entropies} \medskip 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} \smallskip We will denote the set of all the finite measurable partitions of $ ( X \, , \, \mu ) $ by $ \mathcal{P} ( \, X \, , \, \mu \, ) $. \begin{definition} \end{definition} $ A \in \mathcal{P} ( X , \mu ) $ IS FINER THAN $ B \in \mathcal{P} ( X , \mu ) $: every atom of B is the union of atoms by A \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 \; \equiv \; \{ \, 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 ) $. \medskip \begin{remark} \end{remark} COARSE-GRAINED MEASUREMENTS ON A CLASSICAL PROBABILITY SPACE: THE OPERATIONAL MEANING OF A CLASSICAL PARTITION 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 distinguigh events belonging to the same atom of a partition $ A = \{ A_{i} \}_{i=1}^{n} \in \mathcal{P} ( X , \mu ) $. Conseguentially 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 ) $. \smallskip We will call such an experiment an \textbf{operational observation of $ ( X , \mu ) $ through the partition A}. \smallskip 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 \textbf{operational observation of $ ( X , \mu ) $ through the partition A} more simply an \textbf{A experiment}. \medskip \begin{remark} \end{remark} THE DOUBLE MEANING OF THE CLASSICAL PROBABILISTIC SHANNON ENTROPY OF AN 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 Shannon entropy we 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) \equiv H ( \begin{pmatrix} \mu ( A _{1} ) \\ \vdots \\ \mu ( A _{n} ) \ \end{pmatrix} ) \end{equation} with the right hand side expressed in terms of the definition\ref{def:Shannon entropy of a distribution} we introduced in section\ref{sec:Why prefix entropy is better than simple entropy}. 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 \textbf{uncertainty of the experiment}, i.e. the amount of uncertainty on the outcome of the experiment before of realizing it \item the \textbf{information of the experiment}, i.e. amount of information gained by