\documentclass[landscape]{slides}
%\pdfpagewidth=11in
%\pdfpageheight=8.5in
\oddsidemargin=0in
\topmargin=-1in
\textwidth=10in
\textheight=7in
\parskip=0in
\usepackage{pstcol,pst-char,pst-grad}
\usepackage{graphicx,color}
\usepackage{array,amsmath}
\usepackage{euler}

\definecolor{backgroundcolor}{rgb}{.5,0,0}
\definecolor{textcolor}{rgb}{1,1,1}
\definecolor{headcolor}{rgb}{1,1,0}
\definecolor{fillcolor}{rgb}{.8,0,0}
\definecolor{filllcolor}{rgb}{.3,0,0}
%\definecolor{backgroundcolor}{rgb}{1,1,1}
%\definecolor{textcolor}{rgb}{0,0,0}
%\definecolor{headcolor}{rgb}{.3,.3,.3}
%\definecolor{fillcolor}{rgb}{.2,.2,.2}
%\definecolor{filllcolor}{rgb}{.6,.6,.6}

\newcommand{\slt}[1]{\hfill\textcolor{headcolor}{\Large\textbf{#1}}\hfill\hbox{}\vfill\raggedright\par}
\newcommand{\prog}[1]{\texttt{#1}}
\newlength\contboxwidth
\newcommand{\cont}{\setbox0=\hbox{\small\space(continued)}%
	\contboxwidth=\wd0\box0\hspace{-\contboxwidth}}

\let\saveendslide=\endslide
\let\saveendoverlay=\endoverlay
\renewcommand{\endslide}{\vfill\saveendslide}
\renewcommand{\endoverlay}{\vfill\saveendoverlay}
\let\saveslide=\slide
\renewcommand{\slide}{\saveslide\flushright}
\let\saveoverlay=\overlay
\renewcommand{\overlay}{\saveoverlay\flushright}

\newcommand{\godel}{G\"odel}

\title{\textcolor{headcolor}{\Huge\bfseries
Randomness\\{\large and}\\ Mathematical Proof\footnote{%
by Gregory~J.~Chaitin, Scientific American \textbf{232}-5
(May 1975), pp.~47--52, available from
\prog{http://www.cs.auckland.ac.nz/CDMTCS/chaitin/}\\
slides from
\prog{http://behdad.org/download/presentation/chaitin75}}
}}
\author{\vspace{1em}\textcolor{textcolor}{\LARGE
	Behdad Esfahbod\hfill Omid Etesami\\
	\texttt{behdad@behdad.org\hfill etesami@ce.sharif.edu}%
}}
\date{\textcolor{headcolor}{%
Computer Engineering Department\\
Sharif University of Technology\\
Tehran, Iran\\
November 30, 2002
}}

\pagecolor{backgroundcolor}
\color{textcolor}
\begin{document}
\color{textcolor}

\maketitle

\slide
\thispagestyle{empty}
\begin{pspicture}(0,0)(10,10)
\fontfamily{ptm}\selectfont
\pscharpath[fillstyle=gradient,
	gradangle=30,gradbegin=red,gradend=filllcolor,
	linecolor=black,linewidth=1.5pt]
{\fontsize{.85in}{.85in}\selectfont
\parbox{\textwidth}{\begin{center}\bfseries
Although randomness can be precisely defined and can even be
measured, a given number cannot be proved to be
random.
\penalty-50
This enigma establishes a limit to what is possible in mathematics.
\end{center}}}
\end{pspicture}
\endslide

\slide
\slt{What is a Random Sequence?}
\begin{center}
01010101010101010101\\
01101100110111100010
\end{center}
\begin{itemize}
\item Our intuitive notion
\item How we can predict the following numbers?
\item The origin has been random?
\item More sensible definition required, one that does not
contradict the intuitive concept of a ``patternless'' number.
\end{itemize}
\endslide

\slide
\slt{An Algorithmic Definition}
\begin{itemize}
\item Roots in \emph{information theory}
\item A simple example:
	\begin{itemize}
	\item You want to send a friend the trigonometric functions.\\
	You can just send him $e^{ix}=\cos x+i\sin x$, and how to use it.
	\item You want to send her the scores of all the
	major-league games played in the last century.\\
	You have no alternative to sending the entire list of scores.
	\end{itemize}
\item Here we want to communicate with a digital computer.
\end{itemize}
\endslide

\slide
\slt{An Algorithmic Definition\cont}
\begin{itemize}
\item Now there's a difference:
	\begin{itemize}
	\item \prog{print 01 ten times}.\\
		$\rightarrow$ \prog{print 01 a million times}.
	\item \prog{print 01101100110111100010}.\\
		$\rightarrow$ \prog{print 01101100110111100010\ldots}.
	\end{itemize}
\item All random numbers are \emph{incompressible}.
\item Definition proposed independently by A.~N.~Kolmogorov, and
G.~J.~Chaitin in 1960s.
\end{itemize}
\endslide

\slide
\slt{Solomonoff's Model of Inductive Method}
\begin{itemize}
\item A scientist observes a series of binary digits.
\item Then seeks to explain these observations through a theory.
\item This theory, can be regarded as an algorithm.
\item Which can generate the series, and extend them, that is
predicting.
\item There are always several competing theories.
\item The scientist is to choose among them.
\item The model demands that the smallest algorithm be selected.
\end{itemize}
\endslide

\slide
\slt{Example of Inductive Reasoning}
\smash{\hspace{3cm}\hbox to \textwidth{
\hfill
\raisebox{2cm}{\rotatebox{-80}{
\parbox{.9\textheight}{\begin{center}\Huge\bfseries\color{filllcolor}
\quad Given differing theories of apparently equal merit, the simplest
is to be preferred.
\end{center}
}}}}}
\begin{itemize}
\item \textbf{Observations:} 0101010101
\item \textbf{Predictions:} 01010101010101010101\\
      \textbf{Theory:} Ten repetitions of 01\\
      \textbf{Size of Theory:} 21 characters
\item \textbf{Predictions:} 01010101010000000000\\
      \textbf{Theory:} Five repetitions of 01 followed by ten 0's\\
      \textbf{Size of Theory:} 42 characters
\end{itemize}
\endslide

\slide
\slt{The Machine}
\begin{itemize}
\item Different machines communicate through different computer
languages.
\item Sets of instructions expressed in a specific language might
require more or fewer bits than in another language.
\item Any machine can simulate another machine with just a fixed
number of bits.
\item So, the choice of computer matters very little.
\item We choose for our calculations an ideal computer.  Input
and output are in binary.
\end{itemize}
\endslide

\slide
\slt{Minimal Programs}
\begin{itemize}
\item Infinite number of algorithms for generating any specified
series of numbers.
\item The programs of greatest interest, are the smallest ones.
\item The smallest programs are called minimal programs.
\item For a given series, there may be only one minimal program,
or there may be many.
\item What is important is that there always \emph{exists} a
minimal program.
\end{itemize}
\endslide

\slide
\slt{Minimal Programs\cont}
\begin{itemize}
\item Any minimal program is necessarily random, independent of
the series it generates (as we have defined randomness this way).
\item Scenario:
	\begin{itemize}
	\item Program $P$ is a minimal program for series $S$.
	\item If $P$ is not random, by definition there's another
		program $\cal P$, substantially smaller than $P$,
		that will generate it.
	\item Now we can produce $S$ this way: \emph{From $\cal
		P$ calculate $P$, then from $P$ calculate $S$.}
	\item This program is only a few bits longer than $\cal P$.
	\item $P$ is not a minimal program.
	\end{itemize}
\end{itemize}
\endslide

\slide
\slt{Complexity}
\begin{itemize}
\item The complexity of a series is the number of input bits to a
machine.
\item It's therefore equal to the size of the minimal programs of
the series.
\item In our new terms: \textbf{A random series of digits is one whose
complexity is \emph{approximately} equal to its size in bits.}
\item A number with $n$ digits, may be of complexity $n-1$,
$n-10$, $n-100$, \dots.  The exact border between random and
non-random numbers remains somewhat arbitrary.
\end{itemize}
\endslide

\slide
\slt{Properties of Random Numbers}
\begin{itemize}
\item A sequence of length $n$ of all 0's, has complexity of
about $\log_2 n$.
\item A sequence of length $n$, which the relative frequencies of
1's to 0's is three to one, has complexity of about $4n/5$.
\item In any random binary series, the frequencies of 0's and 1's
must be very close to one-half.
\item With a simple calculation, more that 99.9\% of all
$n$-digit numbers are random, for large $n$'s
\end{itemize}
\endslide

\begingroup
\textwidth=\paperwidth
\parindent=0em
\parskip=0em
\vspace*{\stretch{1}}
\textcolor{backgroundcolor}{.}
\includegraphics[width=.95\textwidth,height=.95\textheight,keepaspectratio=true]{greg3b.eps}
\hspace{-1cm}\mbox{}
\vspace*{\stretch{1}}
\endgroup

\slide
\slt{Formal Systems}
\begin{itemize}
\item It's fairly easy to prove that a specific series
is not random; just to find a small program that generates it.
\item To show that a particular series is random, must prove that
no small program exists for calculating it.
\item Chaitin proved that no such proof exists.
\item But, \textbf{what constitutes a valid proof in mathematics,
how is such a proof to be recognized?}
\end{itemize}
\endslide

\slide
\slt{Formal Systems\cont}
\begin{itemize}
\item David Hilbert defined an artificial language, in which
valid proofs could be found mechanically.
\item \godel\ proved that there is no such perfect language.
\item Hilbert's model of a Formal System:
	\begin{itemize}
	\item A finite alphabet of symbols
	\item An unambiguous grammer defining meaningful statements
	\item A finite list of \emph{axioms}, which are initial assumptions
	\item A finite list of \emph{rules of inference}, which
	theorems can be deduced from the axioms or other theorems with
	\end{itemize}
\end{itemize}
\endslide

\slide
\slt{A Formal System}
\begin{center}
\includegraphics{images.mps}
\end{center}
\endslide

\slide
\slt{Unprovable Statements}
\begin{itemize}
\item \godel\ showed in 1931 that Hilbert's plan for a completely
systematic mathematics cannot be fulfilled.
\item Did this by constructing an assertion in Hilbert's formal
system, that is true, but cannot be proved in the system.
\item No matter how large and complicated the system is.
\item Any such system is \textbf{incomplete}.
\item There can be no definitive answer to the question ``What is
a valid proof?''
\end{itemize}
\endslide

\slide
\slt{\godel's Incompleteness Theorem}
\begin{itemize}
\item Based on Epimenides Paradox: \emph{``This statement is
false.''}  This assertion is neither true nor false.
\item \godel\ replaced truth with provability: \emph{``This
statement is unprovable.''}  This assertion is provable if and
only if it is false.
\item Either a falsehood is provable, which is forbidden by the
system, or a true statement is unprovable.
\item So the formal system is incomplete!
\item \godel\ also converted this sentence into an assertion
in Hilbert's formal system.
\end{itemize}
\endslide

\slide
\slt{Chaitin's Proof to \godel's Theorem}
\begin{itemize}
\item Based on Berry Paradox: \emph{``Find the smallest positive
integer which to be specified requires more characters than there
are in this sentence.''}
\item Chaitin replaced truth with provability again: \emph{``Find
the smallest positive integer which can be proved to require more
characters than there are in this sentence.''}
\item In computer terms, it means:  \emph{``Find a series of
binary digits that can be proved to be of a complexity greater
than the number of bits in this program.''}.  And what this
program actually does?
\item Testing all possible proofs in the formal system in order
of their size, until it finds an answer.  So it finds the first
number that it can be proved incapable of finding!
\end{itemize}
\endslide

\slide
\slt{What Does it Really Mean?}
\begin{itemize}
\item The limiting factor is the number of bits in the formal
system as a whole.  The information content of axioms and rules
is the complexity of the formal system.
\item \textbf{In a formal system of complexity $n$, it is impossible to
prove that a particular series of binary digits is of complexity
greater than $n+c$, where $c$ is a constant that is independent
of the particular system employed.}
\item Also, \textbf{no number(program) can be proved to be
random(minimal), unless the complexity of the number(program)
is less than that of the system itself.}
\item Suggests that in order to progress, mathematicians, like
investigators in other sciences, must search for new axioms.
\end{itemize}
\endslide

\slide
\slt{Three Paradoxes}
\begin{itemize}
\item \textbf{Russell Paradox:} \emph{Consider the set of all sets
that are not members of themselves.}  Is this set a member of
itself?
\item \textbf{Epimenides Paradox:} \emph{Consider this statement:
``This statement is false.''}  Is this statement true?
\item \textbf{Berry Paradox:} \emph{Consider this sentence:
``Find the smallest positive integer which to be specified
requires more characters than there are in this sentence.''} Does
this sentence specify a positive integer?
\end{itemize}
\endslide

\slide
\slt{Unprovable Statements}
\begin{itemize}
\item This statement is unprovable.
\item The complexity of 01101100110111100010 is greater than $15$
bits.
\item The series of digits 01101100110111100010 is random.
\item 10100 is a minimal program for the series
11111111111111111111.
\end{itemize}
\endslide

\vspace*{-1in}
\begingroup
\raisebox{-.5\textheight}{
\includegraphics[height=\textheight,keepaspectratio=true]{greg2b.eps}
}
\hfill
\begin{pspicture}(0,0)(9,10)
\fontfamily{ptm}\selectfont
\pscharpath[fillstyle=solid,linecolor=black,
	fillcolor=filllcolor,linewidth=.1pt]
{\fontsize{2in}{2in}\selectfont
\parbox{0\textwidth}{
\bfseries \begin{flushright} THE\\ END \end{flushright}
}}
\end{pspicture}
\hspace*{1cm}
\endgroup

\end{document}

\slide
\slt{}
\begin{itemize}
\item
\end{itemize}
\endslide