% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample5.tex,v 1.22 2004/10/08 14:02:33 tantau Exp $

\documentclass[11pt]{beamer}

%\usetheme{Darmstadt}
%\usetheme{Berkeley}
\usetheme{Montpellier}
%%\usetheme{Marburg}
%%\usetheme{Singapore}
%\usetheme{Hannover}

\usepackage{times}
\usefonttheme{structurebold}

\usepackage[english]{babel}
\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps}
\usepackage{amsmath,amssymb}
\usepackage[latin1]{inputenc}

\usepackage{latexsym}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{url}
\usepackage[scaled=.92]{helvet}  %% chooses appropriately
                                                      %% scaled helvetica font
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\newcommand{\raisedot}{%
  \makebox[0cm][c]{%
  \raisebox{0.19\baselineskip}{\ensuremath{.}}}}

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

\newcommand{\ctr}[1]{\begin{center} #1 \end{center}}
\newcommand{\oo}{\infty}
\newcommand{\al}[1]{\begin{align} #1 \end{align}}
\newcommand{\alx}[1]{\begin{align*} #1 \end{align*}}
\newcommand{\RR}{\mathbf{R}}
\newcommand{\QQ}{\mathbf{Q}}
\newcommand{\NN}{\mathbf{N}}
\newcommand{\CC}{\mathbf{C}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\prf}{\noindent {\em Proof.}  }
\newcommand{\QED}{\hfill $\qed$}
\newcommand{\dom}{\mbox{\rm dom}}
\newcommand{\bin}{\mbox{bin}}
\newcommand{\Iota}{\mbox{{\tiny Iota}}}
\newcommand{\fhalt}{\mbox{{\footnotesize halt}}}
\newcommand{\fFermat}{\mbox{{\footnotesize Fermat}}}
\newcommand{\fGoldbach}{\mbox{{\footnotesize Goldbach}}}

\newcommand{\fRiemann}{\mbox{{\footnotesize Riemann}}}
\newcommand{\fCollatz}{\mbox{{\footnotesize Collatz}}}

\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newcommand{\fdom}{\mbox{\rm \footnotesize{dom}}}
\newcommand{\fbin}{\mbox{\rm \footnotesize{bin}}}


\newcommand{\blds}[1]{\mbox{\scriptsize \boldmath $#1$}}


\setbeamercovered{dynamic}

\newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}

\newcommand{\Class}[1]{\operatorname{\mathchoice
  {\text{\sf \small #1}}
  {\text{\sf \small #1}}
  {\text{\sf #1}}
  {\text{\sf #1}}}}

\newcommand{\NumSAT}      {\text{\small\#SAT}}
\newcommand{\NumA}        {\#_{\!A}}

\newcommand{\barA}        {\,\bar{\!A}}

\newcommand{\Nat}{\mathbb{N}}
\newcommand{\Set}[1]{\{#1\}}


%\logo{\pgfuseimage{logo}}





\colorlet{redshaded}{red!25!bg}
\colorlet{shaded}{black!25!bg}
\colorlet{shadedshaded}{black!10!bg}
\colorlet{blackshaded}{black!40!bg}

\colorlet{darkred}{red!80!black}
\colorlet{darkblue}{blue!80!black}
\colorlet{darkgreen}{green!80!black}


\def\softness{0.4}
\definecolor{softred}{rgb}{1,\softness,\softness}
\definecolor{softgreen}{rgb}{\softness,1,\softness}
\definecolor{softblue}{rgb}{\softness,\softness,1}

\definecolor{softrg}{rgb}{1,1,\softness}
\definecolor{softrb}{rgb}{1,\softness,1}
\definecolor{softgb}{rgb}{\softness,1,1}



\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{MyLightGreen}{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}



\newtheorem{principle}[theorem]{Principle}
\newtheorem{myfact}[theorem]{Fact}
\newtheorem{openproblem}[theorem]{Open Problem}
\def \T  {\mathcal{T}} 

\AtBeginSection[]{\frame{\frametitle{Outline}\tableofcontents[current]}}

\begin{document}


\title{%The Halting Problem and Experimental Mathematics}
Most Programs Stop Quickly or Never Halt}


\author{{ \color{MyDarkBlue} C. S. Calude (University of Auckland)}\\
{ \color{MyDarkBlue} Joint work with M. Stay (University of California Riverside)}}
%\institute[Uni]{{\color{MyDarkBlue}University of Auckland, NZ} }
  \date{}
%  {
 % \color{MyDarkBlue} 
   %Heidelberg, 2006
   %Canterbury, 2007}
   %TAMC07 }}
 %Bucharest, CRM 
%Colloquium UWO, 2007}
%}


% Create the title frame


\frame{\titlepage}

\part{Main Part}
\frame{\frametitle{Outline}\tableofcontents[part=1]}
\section{The halting problem}

 \begin{frame}
   \frametitle{\small  The halting problem}
   
   The halting problem for Turing machines is the problem to decide
whether an arbitrary Turing machine  eventually halts on an
arbitrary input. 

\bigskip \pause


 {\color{MyBlue} Does there exist  a Turing machine $T_{\fhalt}$ which given the code $code(T)$ of a Turing machine $T$,
and the input $x$,  eventually stops and produces $1$ if $T(x)$ stops and $0$
if $T(x)$ does not stop?}  

\bigskip \pause

Turing's (in)famous result states that  \alert{the halting
problem cannot be solved by any Turing machine}, i.e.~there is no
such  $T_{\fhalt}$.


 \end{frame}


\section{Motivation}
\begin{frame}
   \frametitle{\small The halting problem and mathematical knowledge}
   
   
{\color{MyBlue}  How large is the (clearly infinite) set of Turing machines for which we can solve the halting problem?}
   
   \bigskip \pause
   
   
   
   Probabilistically solving the halting problem, even for relatively small-size programs, can be a useful mathematical tool.
   
   \bigskip \pause
   
   
   
   AIT classical approach (Omega and variants) does not provide a 
   solution. {\color{MyBlue}  Is there any other way?}
   \end{frame}
   
  \begin{frame}
 \frametitle{\small A universal prefix-free  machine 1}
A register machine has a finite number of registers, each of which may
contain an arbitrarily large non-negative integer.  The register
machine $U$ (labelled) 
instructions are:

\medskip

L: EQ R1  R2  R3\\
L: SET R1  R2\\
L: ADD R1  R2\\
L: READ R1\\
L: HALT

\end{frame}

\if01
\begin{frame}
 \frametitle{\small A universal prefix-free  machine 2}


A \alert{register machine program}\/ consists of a finite list of
labelled instructions from the above list, with the restriction that
the HALT instruction appears only once, as the last instruction
of the list. \medskip \pause

The input data (a base 16 string) follows immediately
after the HALT instruction.  \medskip \pause

 A program not reading the whole
data or attempting to read past the last data-bit results in a
runtime error. Some programs have no input data. \medskip \pause

\begin{alertblock}{Theorem} The register machine $U$ is prefix-free and universal.
 \end{alertblock}

\end{frame}
\fi
\begin{frame}
 \frametitle{\small Goldbach's Conjecture, Riemann Hypothesis, Collatz's Conjecture}
 %Goldbach's Conjecture, which is part of Hilbert's eighth problem,
 % states   that all positive even integers greater than two can be 
 %expressed as the sum of two primes.  


There exists a program  $T_{\fGoldbach}$ (135 instructions
totalling  3,484 bits)  which never stops iff Goldbach's Conjecture is true. \bigskip \pause


 
 There exists a program $T_{\fRiemann}$  (290
instructions totalling 7,780 bits) which never stops iff   the Riemann Hypothesis is true.\bigskip \pause



There  is a {\it non-constructive}\/ way to prove 
the existence of a program $T_{\fCollatz}$ which never stops iff
the Collatz's Conjecture is true. 
\end{frame}

\if01
  \begin{frame}
 \frametitle{\small Solving exactly the halting program for small-size programs}


Calude-Dinneen (2007) solved the halting problem for all programs for $U$ up to 80 bits in size. Based on this we  computed
the first $43$ bits of its halting probability:   

\[\Omega_{U} = \sum_{U(p)<\infty} 2^{-|p|}\phantom{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx} \]
\[\phantom{xxx}=0.\alert{00010 00000 01000 01010 01110 11100 01000 00101 110.\ldots}\]


\end{frame}
  \fi
  
  \begin{frame}
   \frametitle{\small Main question}
   


 \begin{quote} 
We are given a universal prefix-free machine $U$ and a randomly chosen program $p$ of length $N$ that we know  not to stop by time $t$.

\pause
\medskip

{\color{MyBlue}  Can we effectively evaluate the probability that $U(p)$ eventually stops? }
\end{quote}
   
     
   \end{frame}
   

   
  \section{The time when a program stops}
  
  
  \begin{frame}
 \frametitle{\small  Intuition}
 
It is easy to write a short program that does not stop, but 
\pause

\bigskip
 \alert{it seems difficult to write a short program which \pause
 \begin{itemize}
 \item
 halts, and \pause
 \item
 takes a very long time to stop.
 \end{itemize}}
  \end{frame}
  
  
   \begin{frame}
 \frametitle{\small  A bit of notation}
 
 
Let $\bin(i)$ be the $i$th  binary string: $\bin(1) = $ the empty string, $\bin(2)=0$, $\bin(3) = 1$, $\bin(4) = 00$, $\bin(5) = 01$,\ldots \, \\
and let $$H(x) =H_{U}(x)
 =  \min\{|p| \mid U(p)=x\}$$ be the program-size complexity (induced by $U$).
\end{frame}

\begin{frame}
 \frametitle{\small   Is there a preferred time when a program  can stop?   \hfill 1}
 
 
 
 
 
 \begin{alertblock}{Theorem [Chaitin, 1987]}  There is a constant $c$ such that
if $U(\bin(i))$ halts exactly in time $t$, then $$H(\bin(t)) \le |\bin(i)| +c.$$
 \end{alertblock} \pause


\medskip

Difficulty: \alert{$H$ is not computable.}
\\
\pause
\medskip

Problem: {\color{MyBlue}  Can we ``effectively extract'' any information from the above inequality?}
\end{frame}


\begin{frame}
 \frametitle{\small   Is there a preferred time when a program  can stop?  \hfill 2}
 
A time $t$ is \alert{algorithmically random} if $$H(\bin (t)) \ge |\bin(t)| 
- \log |\bin(t)| .$$

\bigskip \pause

\begin{alertblock}{Fact}
Algorithmically random strings of any length exit. They have effective
density one.
\end{alertblock}

\end{frame}

\begin{frame}
 \frametitle{\small   Is there a preferred time when a program  can stop?  \hfill 3}
\begin{alertblock}{Theorem}
Assume that an $N$-bit program $U(p)$  has not stopped by time $2^{2N+2c+1}$, where $N\ge 2$ and $c$ comes from  Chaitin's theorem. 

Then, 

\begin{center}$U(p)$ cannot stop exactly at any algorithmically random time 

\medskip

$t \ge 2^{2N+2c+1}$.
\end{center}
\end{alertblock}
\end{frame}

\begin{frame}
 \frametitle{\small Density}

  A time $t$ is called ``exponential stopping time'' if there is a program $p$ which stops on $U$ exactly at   time  $t > 2^{2|p|+2c+1}$.  
 
 \bigskip \pause

 \begin{alertblock}{Theorem}
 The set of exponential stopping times has effectively zero density.
\end{alertblock}
\end{frame}


\section{Halting according to a computable time distribution}
\begin{frame}
 \frametitle{\small  Postulate}
 
 We assume
\alert{ an a priori computable probability distribution on all possible
runtimes}: we choose a time $i$ randomly from a probability distribution $\rho(i)$ which effectively converges to 1, that is, there exists a computable function $B$ such that for every $n\ge B(k)$, $$|1-\sum_{i=1}^{n}\rho(i)|< 2^{-k}.$$

\bigskip\pause


Consequently, the probability space is the product of the space of programs  and the time space:
\[Space_{\{\rho_{i}\}} = \{0,1\}^{*} \times \{1,2,\ldots \},\]
\noindent where $N$-bit programs  are assumed to be uniformly distributed, and the observer time flows according  to 
the computable probability distribution  $\{\rho_{i}\}$. 
\end{frame}



\begin{frame}
 \frametitle{\small  Example of a computable time distribution}



For every program $\bin(i)$ let $t\,_{\fbin(i)}$ be the exact time $U(\bin(i))$ stops, if 
 $U(\bin(i)$ halts, or $t\,_{\fbin(i)}= \infty$, otherwise.
 
 \medskip \pause
 
Define the \alert{computable number}:
\[0 < \Upsilon_{U}=\sum_{i\ge 1}2^{-i}/t\,_{\fbin(i)} < 1. \]

\medskip \pause

Then,  define the computable probability distribution 
\medskip 

\[\rho_{i}= \frac{2^{-i}}{t\,_{\fbin(i)}\cdot \Upsilon_{U}}\raisebox{0.5ex}.\]
\end{frame}


\begin{frame}
 \frametitle{\small  Halting probability}

\begin{alertblock}{Theorem} On time we consider  a probability distribution $\rho_{i}$ which effectively converges to 1.
%, that is, there exists a computable function $B$
% such that for every $n\ge B(k)$, $$|1-\sum_{i=1}^{n}\rho_{i}|< 2^{-k}.$$ 
Then, for each $k>0$ we can effectively compute a time $t_{k}$ (which depends upon
$U, \rho$)   such that
the probability that an $N$-bit program which hasn't stopped on $U$ by time $t_{k}$  will eventually halt,
%effectively converges to zero.
 % is not larger than $\sum_{i\ge t_{k}} \rho_{i}$, which effectively converges to 0
  %, that is, there is a computable
  % function $b(k)$ such that for $n\ge b(k)$, $\sum_{i\ge n} \rho_{i} < 
  is smaller than $2^{-k}$.
\end{alertblock}

\bigskip \pause

\begin{alertblock}{Corollary} Assume that  $U(p)$ has not stopped by time $T> k - \lfloor \log \Upsilon_{U} \rfloor$. Then, the probability (according to the above probability space $Space_{\{\rho_{i}\}}$) that $U(p)$ eventually halts is smaller than
$2^{-k}$.
\end{alertblock}
 
\end{frame}





\begin{frame}
 \frametitle{\small Decomposition 1}




\begin{alertblock}{Theorem} Assume that $U$ and $Space_{\{\rho(i)\}}$ have been fixed.  For every integer $k >0$, the set of halting programs for $U$ can be written as  a disjoint union of a computable set and a set of probability effectively smaller than  $2^{-k}$.
\end{alertblock}

\end{frame}

\begin{frame}
 \frametitle{\small Decomposition 2}

The asymptotic density of a set $B$ of one-way Turing machine programs is the limit (if it exists) of the
proportion of all  programs  with $n$ non-final states in $B$ in the set of all programs with $n$ non-final states.

\medskip

\begin{alertblock}{Theorem [Hamkins, Miasnikov, 2006]}
There is a set $B$ of one-way infinite Turing machine programs such that
\begin{enumerate}
 \item $B$ has asymptotic probability one,
 \item $B$ is polynomial time decidable,
 \item The halting problem $H\cap B$ is polynomial time decidable.
\end{enumerate}

\end{alertblock}
\end{frame}

\begin{frame}
 \frametitle{\small Decomposition 3}
 
 

Hamkins--Miasnikov Theorem is machine-dependent.

\medskip

\begin{alertblock}{Theorem [Ryabalov, 2007]}
There is no strongly generic set (i.e.\ its asymptotic density exponentially converges to zero) on which the halting problem is decidable.\end{alertblock}
\end{frame}




\section{Selected references}


\frame{
   %\frametitle{\small  Papers }

  \begin{itemize}
 
\item C. S. Calude, Elena Calude, M. J. Dinneen. A new measure of the difficulty  of  problems,  {\em Journal for Multiple-Valued Logic and Soft Computing} 12 (2006), 285--307.

%\item C.~S. Calude, M.~J. Dinneen. Exact approximations of omega 
% numbers,  {\em Int. Journal of Bifurcation \& Chaos}  17, 6 (2007),
%1--18.

 \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 J. D. Hamkins, A. Miasnikov. The halting problem is decidable on a set of asymptotic probability one, {\em Notre Dame J. Formal Logic}  47, 4 (2006), 515--524.

\item A. Rybalov. On the strongly generic undecidability of the Halting Problem, {\em Theoret. Comput. Sci.} 377 (2007), 268--270.
        \end{itemize}
          }



\end{document}