\documentclass[12pt]{amsart}

\newcommand{\lra}{\longrightarrow}
\newcommand{\Z}{{\mathbf Z}}
\newcommand{\Q}{{\mathbf Q}}
\newcommand{\R}{{\mathbf R}}
\newcommand{\C}{{\mathbf C}}
\newcommand{\mymod}{\,\%\,}

\include{xy}
\xyoption{all}
\SelectTips{cm}{}
\CompileMatrices

\include{iJSepsf}
\newcommand{\graphillus}[3]{\epsfysize=#1truein
\vbox{\centerline{\epsffile{#2.eps}}\caption{#3}}}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{defn}[thm]{Definition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}

\begin{document}

\title{Computable Numbers}
\maketitle

\section{Introduction}

Turing's paper is ``On {\bf computable numbers}, with an application to the
Entscheidungsproblem.''  (Emphasis mine.)  What are computable numbers?

\section{The Definition}

A real number is a Turing machine function
$$
a:\Z^+\lra\Q\times\Q_{\ge0},\qquad n\longmapsto(m_n,e_n).
$$
The classical intuition is that for each positive integer~$n$, the interval
$$
I_n(a)=[m_n-e_n,m_n+e_n]
$$
contains the ``limit'' quantity~$a$.  But really $a$ is a function.
And it must satisfy two conditions:
\begin{itemize}
\item $I_n(a)\cap I_{n'}(a)\ne\emptyset$ for all $n,n'\in\Z^+$.
\item For any $E>0$, it is certain that some $n_0\in\Z^+$ exists
such that $e_n<E$ for all $n>n_0$.
\end{itemize}

\section{Equality}

Two real numbers $a$ and $b$ are equal if
$$
I_n(a)\cap I_{n'}(b)\ne\emptyset\quad\text{for all $n,n'\in\Z^+$.}
$$
The proofs that equality is reflexive and symmetric are immediate.
The proof that equality is transitive requires a small argument.

So in fact a real number is specified by an entire {\em equivalence class}
of functions.

Another small argument shows that trichotomy holds for real numbers.

\section{Algebra}

One can use {\em interval arithmetic} to define addition, subtraction,
multiplication, and division for real numbers.  Examples of interval
arithmetic are
$$
(m_1\pm e_1)+(m_2\pm e_2)=(m_1+m_2)\pm(e_1+e_2)
$$
and
$$
(m_1\pm e_1)(m_2\pm e_2)=(m_1m_2)\pm(|m_1|e_2+|m_2|e_1+e_1e_2).
$$

\section{An Undecidable Problem}

For each Turing maching $M$ define a corresponding number~$a_M$ as follows:
$$
a_M(n)=\begin{cases}
0\pm10^{-n}&\text{if $M$ does not halt within $n$ steps},\\
10^{-h}\pm10^{-n}&\text{if $M$ halts in $h$ steps, where $h\le n$}.\\
\end{cases}
$$
Then $a_M$ is zero if and only if $M$ does not halt.

Suppose that a Turing machine $D$ decides whether real numbers are zero or not.
Then $D$ solves the halting problem.  This is impossible.  Therefore,
the problem of whether an arbitrary real number os zero is undecidable.

\section{Other Nonsolvable Problems}

\begin{itemize}
\item Are two real numbers equal?
\item Is one real number bigger than another?
\item Is one real number at least as big as another?
\item Given two real numbers, which of the three trichotomous relations
between them holds?
\end{itemize}

As an example of this last, consider two real numbers $a$ and~$b$ where
$$
a(n)=0\pm0\quad\text{for all $n$}
$$
and
\begin{align*}
b(1)&=0.0\pm1\quad\text{i.e., $b(1)=[-0.1,0.1]$}\\
b(2)&=0.00\pm1\quad\text{i.e., $b(2)=[-0.01,0.01]$}\\
b(3)&=0.000\pm1\quad\text{i.e., $b(3)=[-0.001,0.001]$}\\
&\vdots
\end{align*}
Is $b$ positive, negative, or zero?  We don't know.  It could be the case
that
$$
b(n)=0\pm10^{-n}\quad\text{for all $n$},
$$
in which case $b=a=0$.  But, for example, it could also be the case that
for some large~$N$,
$$
b(n)=10^{-N}\pm10^{-n}\quad\text{for all $n\ge N$},
$$
in which case $b=10^{-N}>0$.  And similarly, $b$ could well be $-10^{-N}$
for some large~$N$.

\section{Solvable Problems}

\begin{itemize}
\item Given real numbers $a$, $b$, and a positive integer~$k$, choose a true
statement among the three possibilities
$$
a>b,\quad|a-b|<\pm10^{-k},\quad a<b.
$$
Note that the possibilities are not mutually exclusive.
\end{itemize}

\end{document}
