Damon_Notes.tex

\documentclass[11pt]{article}

\usepackage{tikz-cd}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}

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

\usepackage{color}
%\usepackage{graphicp}
%\usepackage{setspace}
\usepackage[top = 2.75cm, bottom = 2.50cm, left   = 2.00cm, right  = 2.00cm]{geometry}
%\doublespacing
\newcommand{\df} [2]{\frac{d#1}{d#2}}
\newcommand{\pdf}[2]{\frac{\partial#1}{\partial#2}}
\newcommand{\fcy}[1]{\mathcal{#1}}
\newcommand{\bb}[1]{\mathbb{#1}}
\newcommand{\nm}[1]{\left\|#1\right\|}
\newcommand{\ilm}[1]{\lim_{#1\rightarrow\infty}}
\newcommand{\bo}[1]{{\bf #1}}
\newcommand{\ra}{\rightarrow}

\newcommand{\ak}{\alpha}        \newcommand{\Ak}{\Alpha}
\newcommand{\bk}{\beta}         \newcommand{\Bk}{\Beta}
\newcommand{\gk}{\gamma}        \newcommand{\Gk}{\Gamma}
\newcommand{\dk}{\delta}        \newcommand{\Dk}{\Delta}
\newcommand{\ek}{\varepsilon}   \newcommand{\Ek}{\Epsilon}
\newcommand{\zk}{\zeta}         \newcommand{\Zk}{\Zeta}
\newcommand{\hk}{\eta}          \newcommand{\Hk}{\Eta}
\newcommand{\qk}{\theta}        \newcommand{\Qk}{\Theta}
\newcommand{\ik}{\iota}         \newcommand{\Ik}{\Iota}
\newcommand{\kk}{\kappa}        \newcommand{\Kk}{\Kappa}
\newcommand{\lk}{\lambda}       \newcommand{\Lk}{\Lambda}
\newcommand{\m}{\mu}            \newcommand{\M}{\Mu}
\newcommand{\n}{\nu}            \newcommand{\N}{\Nu}
\newcommand{\p}{\pi}            \newcommand{\X}{\Xi}
\newcommand{\rk}{\rho}          \newcommand{\Rk}{\Rho}
\newcommand{\sk}{\sigma}        \newcommand{\Sk}{\Sigma}
\newcommand{\tk}{\tau}          \newcommand{\Tk}{\Tau}
\newcommand{\fk}{\phi}          \newcommand{\Fk}{\Phi}
\newcommand{\ck}{\chi}          \newcommand{\Ck}{\Chi}
\newcommand{\yk}{\psi}          \newcommand{\Yk}{\Psi}
\newcommand{\wk}{\omega}        \newcommand{\Wk}{\Omega}

\newcommand{\nb}{\partial}      \newcommand{\Nb}{\nabla}

\newcommand{\nas}{\bo{NAS}_\bullet}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{Skeleton of notes on the Computable Reals}
\author{Damon Binder \\
u5591488}
\maketitle

\section{Definitions}

\begin{defn} The set of finite binary strings is $\bb B_F$ and the set of binary strings is $\bb B$.\end{defn}

\begin{defn} Let $\bb O$ be the set of outputs --- a (possibly infinite) string from the set $\{0,1,\emptyset\}$.\end{defn}

The interpretation of $\bb O$ is that at any step of computation, a computer can do three things --- output $0$
, output $1$, or do nothing, represented by outputting $\emptyset$.

\begin{defn} A \bo{model of computation} $L$ is a map $\bb B_F \rightarrow \bb O$. A program $P$ is an element of $\bb B_F$, and its output is $L(P)$.\end{defn}

\begin{defn} We say a program $P$ \bo{halts} if $L(P)$ is finite.\end{defn}

\begin{defn} We say a program $P$ is \bo{numerical} if $L(P)$ does not end with an infinite string $\emptyset\emptyset\emptyset...$ \end{defn}

\begin{defn} Given a model of computation $L$, a number $x\in[0,1]$ is an \bo{L--computable number} if there exists a numeric program $P$ for which $L(P)$ with the $\emptyset$ stripped away is just the binary representation of $x$. We will represent the set of definable numbers by $\bb R^L$.\end{defn}

\begin{prop} The set $\bb R^L$ is countable. \end{prop}

\begin{defn} We say a model of computation is \bo{expressive} if it can do for loops, if statements, and finite list manipulations. In particular, Turing machines are expressive, as are Turing machines equipped with an oracle.\end{defn}

Need to talk about
\begin{enumerate}
\item How to define an $L$-computable function.
\item How to write algorithms nicely, and convert between an algorithmic approach and an abstract approach.
\item The idea that a number is a single program $P$ vs a function $f$ which takes a number $n$ and spits out the $n^{\text{th}}$ digit.
\item Why various approaches to computation are equivalent --- different alphabets, $\bb R$ vs $[0,1]$ and so on.
\end{enumerate}

\section{Halting and Equality}

\begin{thm} If $L$ is expressive, there does not exist a computable surjection from $\bb N$ to $\bb R^L$.\end{thm}

This is proved via Cantor diagonalization.

\begin{defn} A halting function on $L$ is an $L$--computable function $H$ so that $H(P)$ is $1$ if $P$ halts and $0$ otherwise.\end{defn}

\begin{thm} If $L$ contains a halting function, then there exists a computable surjection from $\bb N$ to $\bb R^L$.\end{thm}

\begin{cly} An expressive language cannot contain a halting function. \end{cly}

\begin{defn} An equality function $E$ takes two numerical programs, $P_1$ and $P_2$, and returns $1$ if $L(P_1) = L(P_2)$ and zero otherwise. \end{defn}

\begin{thm} Possessing an equality function is equivalent to possessing a halting function.\end{thm}

\begin{cly} An expressive language cannot contain an equality function. \end{cly}

\section{Continuity}

\begin{defn} We say an $L$-computable function $f:\bb R^L\ra\bb R^L$ is continuous if there exists a continuous function $g:\bb R\ra \bb R$ so that for any $x\in\bb R^L$, $f(x) = g(x)$.\end{defn}

\begin{lemma} If an $L$-computable function $f$ is not continuous, then there is an $L$ computable sequence which bears witness to this. \end{lemma}

\begin{thm} If $L$ is expressive, then every $L$-computable function from $\bb R^L\ra \bb R^L$ is continuous. \end{thm}

\section{Oracles}
Define $C = C_0$ to be a Turing complete model of computation. We can then recursively define $C_n$ to be $C_{n-1}$ with a halting oracle added. Each of these $C_n$'s is expressive. A neat thing about this hierarchy is relativization --- many statements about $C$ can be proved for $C_n$ in a manner completely analogous to $C$.

\begin{prop} Checking whether an algorithm $P$ is numerical in finite time requires $C_2$ computation power.\end{prop}

\begin{thm} In $C_1$, there exists for every finite subset $A\subset\bb R^{C_0}$ an algorithm which checks in finite time whether $x\in\bb R^{C_0}$ is in $A$. In $C_2$ there exists for every $C^0$-computable subset $A\subset\bb R^{C_0}$ an algorithm which checks whether $x\in\bb R^{C_0}$ is in $A$. In general, in $C^{m+n+2}$ there exists an algorithm for deciding in finite time whether $x$ is in any $C_n$-computable subset of $\bb R^{C_m}$.\end{thm}

\begin{cly}To check whether $x\in\bb R^C$ is rational requires an algorithm of power $C_2$. \end{cly}

\begin{thm}There is no $C_{n+1}$ computable map between $\bb R^{C_n}$ and $\bb R^{C_{n+1}}$.\end{thm}

\bo{Computable Continuum Hypothesis:} Can there exist models of computation $L_1$ and $L_2$ with $\bb R^{L_1}\subset\bb R^{L_2}$, so that no $L_2$ computable surjections exist between $\bb N\ra\bb R^{L_1}$ and also $\bb R^{L_1}\ra \bb R^{L_2}$?


\section{Further Stuff}
We could generalize the notion of an alphabet to allow countable elements in an alphabet. This for instance could allow us to consider adding countable halting oracles onto a model of 
computation. Since the number of such programs is still countable, we still only have a countable number of computable numbers in these models.

Extending even further, we could consider uncountable alphabets. For instance, we have the first expressive uncountable language, which has a halting oracle for each countable halting level. If the continuum hypothesis is false, this cannot be the reals. I don't know whether this will give you the reals, assuming the continuum hypothesis, or other set theoretic axioms, to be true.

There are oracles which are very different to the halting oracles we have considered. Take, for instance God's number $\ak$; it could be any non-computable number in $\bb R$. We could add on an oracle which allows us to compute $\ak$.

There are oracles which are very different to the halting oracles we have considered. Take, for instance God's number $\ak$; it could be any non-computable number in $\bb R$. We could add on an oracle which allows us to compute $\ak$. If Church-Turing thesis is false, it is possible to imagine a physical constant that we could measure, but could not compute. This gives us a physically plausible model of God's number. On the other hand, it is hard to imagine a physical universe where we have a halting oracle, but maybe I just lack imagination.
\end{document}