\documentclass{beamer}
%\documentclass[handout]{beamer}
%\documentclass[draft]{beamer}
%\includeonlyframes{SimulTheorem}
\newcommand{\dom}{{\rm dom}}
\newcommand{\N}{{\bf N}}
\newcommand{\D}{\Delta}
\def \T  {\mathcal{T}} 
\newcommand{\fbin}{\mbox{\rm \footnotesize{bin}}}

\newenvironment{alertitemize}%
  {\begin{itemize}[<+-| alert@+>]}%
  {\end{itemize}}
\newcommand\stopalert{\onslide<+| handout:0>}

\usepackage{geometry} 
% Load a theme for the presentation
%\usepackage{beamerthemeshadow}
\mode<article> % only for the article version
{
  \usepackage{fullpage}
  \usepackage{hyperref}
}

  \mode<presentation>
{% \usetheme{Bergen}%{AnnArbor}
 % \usetheme{Ilmenau}%{AnnArbor}%{Darmstadt}
\usetheme{Boadilla}
  \usefonttheme[onlysmall]{structurebold}
  %\usecolortheme{beaver}%seahorse}
  \usecolortheme{crane}
 \usecolortheme{whale}
  %\usecolortheme{sidebartab}
    \setbeamertemplate{background canvas}[vertical shading][bottom=red!10,top=blue!10]
 }
 
 
  \usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
\usepackage{amsmath,amssymb}
\usepackage[latin1]{inputenc}
\usepackage{colortbl}
\usepackage[english]{babel}

\newcommand{\bin}{\mbox{\rm  bin}}

\definecolor{MyDarkBlue}{rgb}{0,0.08,0.45}
\definecolor{MyBlue}{rgb}{0,0,1}
\definecolor{MyLightMagenta}{cmyk}{0.1,0.8,0,0.1}
\definecolor{MyGreen}{rgb}{0,0.9,0.1}
\definecolor{MyYellow}{rgb}{0.7,0.8,0.1}
\definecolor{MyDarkGreen}{rgb}{0,7.0,0.2}
\definecolor{MyLightBlue}{rgb}{0,0.8,0.9}
\definecolor{MyGray}{cmy}{1,1,0.8}
\definecolor{MyBrick}{rgb}{0.4,0,0.3}
\definecolor{MyWhite}{rgb}{255,255,255}

\newcommand{\raisedot}{%
  \makebox[0cm][c]{%
  \raisebox{0.19\baselineskip}{\ensuremath{.}}}}


\title{Algorithmic versus Quantum Randomness}
\author{Cristian~S.~Calude}
\date{Vienna, November 2007}

\begin{document}
\frame{\titlepage}
\frame{
 \frametitle{\small Summary \hfill 1}
 
 In non-scientific parlance, the word random is used to express lack of order, purpose, cause, or predictability.\pause\medskip
 
 
Ramsey theory shows \alert{there is no such thing as  ``true randomness''.} \pause\medskip

\alert{Algorithmic randomness}, probably the best model of  'randomness',  was intensively studied in the last 40 years by algorithmic information
 theory. \pause\medskip

\alert{Quantum randomness} is the only   `real' source of genuine randomness.}

\frame{
 \frametitle{\small Summary \hfill 2}

We  will
 present new results and open questions related to the following fundamental problems: \pause\medskip

\alert{Is quantum 
 randomness algorithmic random?}\pause\medskip

\alert{How powerful is 
 a  Turing machine supplied with a finite, but unbounded source of quantum random bits?}

}
% ----------------------------------
% Create the outline frame
% ----------------------------------
\section*{Outline}
\frame{\tableofcontents}


% ----------------------------------
% Synopsis
% ----------------------------------

%\section{Synopsis}

\section{Randomness}

\begin{frame}


\begin{itemize}
\item  Weird.  ``The system's been behaving pretty randomly''.\pause

\item Undistinguished.  ``Who was at the conference?'' ``Just a bunch of random business types''.
\pause

\item Unproductive.   ``He's just a random loser''. \pause

\item  Incoherent.  ``That's a random name for that function''. \pause

\item In no particular order. ``The I/O channels are in a pool, and when a file is opened one is chosen randomly''. \pause

\item  Arbitrary. ``It generates a random name for the scratch file''.  \pause

\item   A random hacker.  Teenager soaking up computer time and generally getting in the way. \pause
\item
(MIT usage) One who lives at Random Hall. \pause
\item \ldots   \end{itemize}
\end{frame}

%\section{Finite (algorithmically)  random strings}
%\section{Infinite  (algorithmically)  random sequences}
\section{Algorithmic randomness}

\begin{frame}
   \frametitle{\small Finite algorithmic random bit-strings \hfill 1}
   
   The entire ``philosophy''  of AIT is to equate ``randomness'' with \alert{incompressibility}.
   
   \pause\medskip
   
   
   A bit-string  is (algorithmic) $c$--random if a universal Turing machine cannot compress it
   by more than $c$ bits. The constant $c$ should be less than the logarithm of the length of the string.
   
   
      \pause\medskip
      
      
      Convention: \alert{we will drop the adjective ``algorithmic''}.
   \end{frame}
   
   \begin{frame}
   \frametitle{\small Finite algorithmic random bit-strings \hfill 2}

   
   
Suppose someone
claims to have tossed a fair coin 64 times and the result is:
\begin{center}
 01010101010101010101010101010101
 01010101010101010101010101010101
\end{center}
\pause

\noindent Then, the experiment is repeated and the result is:
\begin{center}
10101010100100101010010110110001
10001100111100110011111000011011
\end{center}
\pause

We  would be surprised/suspicious about the first result, but less/not
about the second one. \pause Why? \pause\\
\medskip

A  flawed explanation:
the probability of obtaining the first result is  $2^{-64}$, so it is
unreasonable to believe that it has been produced by a real
experiment!

 \end{frame}
   
   \begin{frame}
   \frametitle{\small Finite algorithmic random bit-strings \hfill 3}


 The difference between the above results   \alert{is not} probabilistic, but \alert{structural:}
 while the first string is ordered,
there is no apparent pattern in the second.
   
     
   
      \end{frame}
   
   \begin{frame}
   \frametitle{\small Expected properties of finite  random bit-strings \hfill 1}

   Finite  random bit-strings have the following expected properties:
   
   \begin{itemize}
   \item \alert{Abundance:}
 almost every bit-string is random (density one).\pause
   \item  \alert{Unpredictability:}
 no Turing machine can compute the $i$th bit of a  random string based on its first $i-1$ bits.
   \pause 
 \item \alert{Statistically unbiased:}
 they  satisfy all computable enumerable statistical properties of randomness. \pause
   \item \alert{Uncomputability:}
 no Turing machine can check whether a string is random or not.
   \pause 
   \item \alert{Strong uncomputability:}
 no Turing machine can generate infinitely many random  strings.\pause 
  
 %  \item \pause 
    \end{itemize}
    \end{frame}

   
      
   \begin{frame}
   \frametitle{\small Unexpected properties of finite  random bit-strings}

  Finite  random bit-strings have the following unexpected properties:


\begin{itemize}
\item
   Halting times are not random:  no Turing machine that stops on an input of $n$ bits after a time larger than $2^{2n+3}$ stops at  a \alert{random time}. \pause
 \item Every  ``decent'' Monte Carlo simulation algorithm (like Rabin's primality test) powered with algorithmic randomness produces the correct result 
not only  with high probability, but \alert{ rigourously correct}.  

\end{itemize}
  \end{frame}

   
      
   \begin{frame}
   \frametitle{\small Infinite  random sequences}

A sequence $x_{1}x_{2}\cdots $ is random if there is a $c>0$ such that each of its 
prefixes is $c$--random. \medskip\pause


Random sequences

\begin{itemize}
\item satisfy \alert{all} computable enumerable statistical properties of randomness, \pause
\item are \alert{unpredictable},  \pause
\item are \alert{uncomputable},  \pause
\item \alert{abound} (have measure one).
\end{itemize}


 \end{frame}
 



\begin{frame}[label=omega]
   \frametitle{\small   Example  of an  infinite  random sequences}
   
   The infinite binary expansion of the halting probability of a prefix-free universal Turing machine $U$, Chaitin's Omega number, 
   
   \[\Omega_{U} = \sum_{U(x) \mbox{  stops  }} 2^{-|x|}\]
   
   \noindent is  random.
   \medskip\pause
   
   
  With the first $n$ bits of $\Omega_{U}$ one can solve the halting problem for $U$ and  all programs of less than $n$ bits. \hyperlink{omegaknowledge}{\beamergotobutton{Examples}}
\end{frame}


\section{Quantum randomness}


\begin{frame}[label=qrand]
  \frametitle{\small   Quantum  randomness}
  \pause
 \begin{itemize}
 \item It is \alert{postulated} in the standard model of quantum mechanics.\pause

 \item It has been \alert{confirmed}  by theoretical and experimental research. \pause
 \item It passes \alert{all reasonable} statistical properties  of randomness. \pause
 %\item
 % It is \alert{Turing uncomputable}. \pause
\item  Can be \alert{easily and reliably  produced}: A photon generated by a source   beamed to a semitransparent mirror
is reflected or transmitted with 50 per cent chance, and these measurements can be  translated into a string of quantum random bits.\hyperlink{quantis}{\beamergotobutton{Quantis}}
     \end{itemize}
 \end{frame}






\section{Is quantum randomness algorithmically random?}

\begin{frame}[label=qranduncomput]
   \frametitle{\small  Quantum randomness is not computable}
   \pause
   \begin{itemize}
 \item  Computer generated randomness is \alert{computable} (John von Neumann: ``Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin''.).
\pause
 \item Quantum generated randomness is \alert{uncomputable}.
   \pause
 \item   Uncomputability is a strong property, but it does not necessarily imply  algorithmical incompressibility. \pause   
 
 \medskip \alert{Is quantum randomness algorithmically random?} 
   \end{itemize}
   
\end{frame}

\begin{frame}
   \frametitle{\small  How `random' quantum randomness?}
   
 \begin{quote}  \alert{Can finite tests distinguish between computable and uncomputable randomness?}
 \end{quote}
 
  \medskip
  
  \pause
  
  Various tests 
  \begin{itemize}
  \item standard: DieHarder, TESTU01 Crush and BigCrush tests,
 \item AIT--based
 \end{itemize}
 
 have been done with six $2^{32}$-bit strings
  produced by Quantis (2), Mathematica (2), C and $\pi$.
  
  \medskip
  \pause
  
  To date \alert{Quantis and Mathematica generated randomness are very close.} More testing is in progress.
   
\end{frame}

\begin{frame}
   \frametitle{\small  A PC powered with quantum random bits}
   
Plug  quantum random bits into a PC and we can, in theory at least, leapfrog Turing's barrier.


  \medskip
  \pause
 

Is this interesting?  

\medskip
  \pause



\alert{How much more powerful  a Turing machine  working with  ``an oracle of quantum  random bits'' can be?}

\medskip\pause

This machine could, at any time,  ask the ``oracle of quantum  random bits'' to supply  an arbitrarily long (but finite)  string.  It won't have access to an infinite sequence, but to an unbounded  finite set of 
strings of quantum random bits.

\end{frame}









\frame{
   \frametitle{\small   References  }
 
  \begin{itemize}
  \item C. S. Calude.  Algorithmic randomness, quantum physics,  and incompleteness,
in M. Margenstern (ed.). {\em Proc. Conf. ``Machines, Computations and Universality''}, 
Lectures Notes in Comput. Sci. 3354, Springer, Berlin, 2005, 1--17.
         \item C.~S. Calude, J. Casti. The jumble cruncher, {\em  New Scientist},  25 September 2004, 36--37.

 \item C. S. Calude, H. J{\"u}rgensen.  Is complexity a source of incompleteness?
{\em Advances in Applied Mathematics} 35 (2005), 1--15.
       
          

\item C. S. Calude, M. A. Stay. Most 
programs stop quickly or never halt, {\em Adv. Appl. Math.}, (2007), doi:10.1016/j.amm.2007.01.001.

\item C. S. Calude, K. Svozil. Quantum randomness and value indefiniteness, {\em Advanced Science Letters}, accepted.
\item K. Svozil. The quantum coin toss-testing microphysical undecida- bility, {\em Phys. Lett. A} 143 (1990),  433--437.
  \end{itemize}
  }

\begin{frame}[label=omegaknowledge]
\begin{itemize}
\item With  3,484 bits one can solve Goldbach's Conjecture.
\item With  7,780 bits one can solve the Riemann Hypothesis.
\end{itemize}
\hyperlink{qrand}{\beamergotobutton{Quantum randomness}}
\end{frame}

\begin{frame}[label=quantis]
   \frametitle{\small  Quantis}
  
  \begin{columns}
  
 \column{7.5cm}

  \includegraphics[width=2.6in]{quantis.pdf}
  
  
\column{3.5cm}
  
  Quantis: 16Mbits/sec quantum mechanical random number generator produced and sold by  {\it id Quantique} of the  University of Geneva
  
  \end{columns}
  
   
  
  
  \hfill \hyperlink{qranduncomput}{\beamergotobutton{Quantum randomness}}
  \end{frame}

\end{document}

\begin{frame}
   \frametitle{\small}
   
   \end{frame}