Halting_is_Equality.tex

\documentclass[a4paper,12pt]{article}
\usepackage{amssymb, algorithm, fancyhdr, algorithmicx, algpseudocode}

\newcommand{\m}{\mathbb}
\newcommand{\B}{\mathcal}

\newtheorem{name}{Printed output}[section]
\newtheorem{mydef}{Definition}[section]
\newtheorem{mylem}{Lemma}[section]
\newtheorem{mythm}{Theorem}[section]
\newtheorem{mycor}{Corollary}[section]

\pagestyle{fancy}
\setlength{\parindent}{0mm}
\setlength{\headheight}{15.0pt}
\lhead{Angus Gruen, u5561004}
\rhead{Comparing $\m{R}^{eq}$ and $\m{R}^{halt}$}

\begin{document}
	\begin{mythm} \label{halt_eq_equaltity}
		For a given computation model $L$, a halting program $H$ exists if an only if an equality program $E$ exists.
	\end{mythm}

	This is a two step proof. For simplicity let $a, b$ be two computable numbers in $[0, 1]^{L}$ with corresponding programs $P_a$ and $P_b$. Let $\B Q$ be the following program taking inputs $P_a, P_b$

	\begin{algorithm}
		\caption{$Q(P_a, P_b)$}
		\label{Q}
		\begin{algorithmic}
			\State acc = 1
			\While {$P_a(acc) = P_b(acc)$}
				\State acc += 1
			\EndWhile
			\If {$P_a(acc) = P_b(acc) + 1$}
				\State acc += 1
				\While {$P_a(acc) = 0$ and $P_b(acc) = 1$}
					\State acc += 1
				\EndWhile
			\ElsIf {$P_a(acc) = P_b(acc) - 1$}
				\State acc += 1
				\While {$P_a(acc) = 1$ and $P_b(acc) = 0$}
					\State acc += 1
				\EndWhile
			\EndIf
			\State \Return {False}
		\end{algorithmic}
	\end{algorithm}

	Clearly, $Q$ will halt and return False if and only if $a \neq b$. Hence $H(Q(P_a, P_b))$ is an equality function on $[0, 1]^{L}$.

	\vspace{2mm}

	Next given a program $P$ and an input $I$ define the number $a$ by the following program $R$ which accepts an input $n \in N$.
	\begin{algorithm}
		\caption{$R(n)$}
		\label{R}
		\begin{algorithmic}
			\State{Run the program $P$ with input $I$}
			\If {$P$ has halted before $n$ seconds}
				\State \Return 1
			\Else
				\State \Return 0
			\EndIf
		\end{algorithmic}
	\end{algorithm}
	Then the program $P$ does not halt on input $I$ if and only if $a = 0$. Hence $E(0, R)$ is a halting function.

	\vspace{2mm}

	This proves Theorem \ref{halt_eq_equaltity} for all $\Omega$ that allow for Algorithms \ref{Q} and \ref{R}. 
\end{document}