\documentclass[a4paper,10pt]{article}
\usepackage{amsfonts}
\title{CS-226 Computability Theory, Coursework 1}
\author{Sean Handley, 320097@swan.ac.uk}
\date{March 2006}
\begin{document}
   \maketitle

\section{}
\subsection{Show that, if $A$ is finite, then $|\mathcal{P}(A)| = 2^{|A|}$}

Suppose A = $\emptyset$
\newline\newline
$\mathcal{P}(A)$ = \{$\emptyset$\} therefore $|\mathcal{P}(A)| = 1$
\newline\newline
$|A| = 0$
\newline\newline
$|\mathcal{P}(A)| = 2^{0} = 1$
\newline\newline
The base case holds.
\newline\newline
Suppose $A = {a} \cup B, a \notin B$ therefore $|A| = |B| + 1$
\newline\newline
$|\mathcal{P}(B)| = 2^{|B|}$ and $|\mathcal{P}(A)| = 2^{|B+1|}$
\newline\newline
Therefore:
\newline\newline
$\mathcal{P}(A) = \mathcal{P}(B)$ + induction step (+1)
\newline\newline
$2^{|B+1|} = 2^{|(B+1)|}$
\newline\newline
Therefore the induction step holds and $|\mathcal{P}(A)|$ is always equal to $2^{|A|}$ where $A$ is finite.

\subsection{Show that $|A| \neq |\mathcal{P}(A)|$.}

If $|A| = |\mathcal{P}(A)|$ holds true for any value, then it contradicts the proof in 1.1, which is not intuitively feasible.
\newline\newline
However, suppose $|A| = |\mathcal{P}(A)|$.
\newline\newline
Let $A = \emptyset$.
\newline\newline
$|\mathcal{P}(A)| = 2^{|A|}= 2^{0} = 1$
\newline\newline
But $|A| = 0$, a contradiction.
\newline\newline
Therefore, we can conclude that $|A| \neq |\mathcal{P}(A)|$.

\section{Define for sets $A,B$ that $A \leq B$ if, and only if, there exists an injective function $f: A \rightarrow B$. Show that $\leq$ is reflexive and transitive. Is $\leq$ symmetric? Prove your answer.}

Def: $A \leq B \iff f : A \rightarrow B$ s.t. $\forall a, f(a) \rightarrow f(b), a \in A, b \in B$\newline\newline

Reflexivity:\newline\newline

$A \leq B \sim A' \leq B' $\newline\newline
if, and only if, there exists an injective function\newline\newline

$f : A \rightarrow A' $ s.t. $\forall a, \forall a' , f(a) \rightarrow f(a'), a \in A, a' \in A' $\newline\newline

and $f : B \rightarrow B' $ s.t. $\forall b, \forall b' , f(b) \rightarrow f(b'), b \in B, b' \in B' $\newline\newline

Transitivity: $A \leq B, B \leq C \rightarrow A \leq C$\newline\newline

$f : A \rightarrow B$ s.t. $\forall a, f(a) \rightarrow f(b), a \in A, b \in B$\newline\newline

$f : B \rightarrow C$ s.t. $\forall b, f(b) \rightarrow f(c), b \in B, c \in C$\newline\newline

$f : A \rightarrow C$ s.t. $\forall a, f(a) \rightarrow f(c), a \in A, c \in C$\newline\newline

Symmetry: $A \leq B \sim B \leq A$\newline\newline

Suppose $|A| \leq |B| \sim |B| \leq |A|$\newline\newline

According to the above definition,\newline\newline

$A \leq B \iff f : A \rightarrow B$ s.t. $\forall a, f(a) \rightarrow f(b), a \in A, b \in B$\newline
and $B \leq A \iff f : B \rightarrow A$ s.t. $\forall b, f(b) \rightarrow f(a), a \in A, b \in B$.\newline\newline

Assuming $\leq$ is indeed a symmetric relation, then it must also be a bijection. Therefore $\leq$ is always symmetric where $|A| = |B|$.\newline\newline

Now we must prove $|A| \leq |B| \sim |B| \leq |A|$ where $|A| \neq |B|$. Put more simply, $|A| < |B| \sim |B| < |A|$.\newline\newline

Proof by induction.\newline\newline

Let $|A| = 0$. This means $|B| > 0$. Let $|B| = 1$.\newline\newline

This holds true for $|A| < |B|$ but not for $|B| < |A|$, giving a contradiction. If we change our original conjecture to $|A| < |B| \not\sim |B| < |A|$ then the base case holds and we can move on to the induction step.\newline\newline

Suppose $A = {a} \cup B, a \notin B$ therefore $|A| = |B| + 1$\newline\newline

This means $|B| < |A|$ because $|A|$ is always bigger than $|B|$ by one. Consequently, $|A| < |B|$ can never happen. Therefore, $<$ is never symmetrical and $\leq$ is only symmetrical when $A$ and $B$ are equinumerous.

\section{Which of the following sets are countable? Prove your answer.}
A set is countable if it is finite or is equinumerous with $\mathbb{N}$.
\subsection{The set $A := \{n \in \mathbb{N} | n \geq 5\}$.}
$\mathbb{N}$ is countable, therefore $\mathbb{N}-\{1,2,3,4,5\}$ is also countable because $|\mathbb{N}| > |\mathbb{N}-\{1,2,3,4,5\}|$.
\subsection{The set $\mathcal{P}(A)$ where $A$ is as in 3.1.}
$\mathcal{P}(A)$ is not countable because $\mathcal{P}(\mathbb{N})$ is not countable.
\subsection{The set $B := \{n \in \mathbb{N} | \leq 5\}$.}
This is countable because it is the set \{1,2,3,4,5\}.
\subsection{The set $\mathcal{P}(B)$ where $B$ is as in 3.3.}
This is countable because it is finite.
\subsection{The set of finite subsets of $\mathbb{Z}$.}
This is not countable because the set of finite subsets of $\mathbb{Z}$ is not equinumerous with $\mathbb{N}$
\subsection{$\mathcal{P}(\mathbb{Z})$.}
This is not countable because it is not equinumerous with $\mathbb{N}$.
\subsection{The set of infinite subsets of $\mathbb{Z}$.}
This is not countable because it is not equinumerous with $\mathbb{Z}$.
\subsection{The set $C := \{f | f : \mathbb{N} \rightarrow \{0,1,2\}\}$.}
This set is countable because it is equinumerous with $\mathbb{N}$. This is provable because there exists a bijection $f : \mathbb{N} \rightarrow \{0,1,2\}$.
\subsection{The set $D := \{(x_{0},...,x_{n-1}) \in \mathbb{N}^{*} | n \in \mathbb{N}, x_{i} \in \mathbb{N}, x_{i} \neq x_{j},$ for $i \neq j\}$.}
This is the set of all strings over $\mathbb{N}^{*}$ where each string is made up of unique natural numbers. It is countable.

\section{Determine a URM program which computes the function $f : \mathbb{N} \rightarrow \mathbb{N}, f(x) := 2 \cdot x$. Justify your answer.}

$I_{0} = iszero(0,5)$\newline
$I_{1} = succ(1)$\newline
$I_{2} = succ(1)$\newline
$I_{3} = pred(0)$\newline
$I_{4} = iszero(2,0)$\newline
$I_{5} = iszero(1,11)$\newline
$I_{6} = succ(2)$\newline
$I_{7} = succ(0)$\newline
$I_{8} = pred(1)$\newline
$I_{9} = iszero(1,11)$\newline
$I_{10} = iszero(3,6)$\newline

If $R_{0} = 0$ then $2 \cdot x = 0$. Execution jumps to $I_{5}$ which jumps to $I_{11}$ because $R_{1}$ is zero. This ends the execution.

If $R_{0} > 0$ then $I_{0}$ returns $false$ and execution moves to $I_{1}$. $I_{1}$ and $I_{2}$ each increment $R_{1}$ by one. $I_{3}$ decrements $R_{0}$ by 1. At this point, $I_{4}$ checks if $R_{2}$ is zero, which it should be. This returns us to $I_{0}$ and the process loops until $R_{0} = 0$, leaving $R_{1}$ holding double the value that was initially in $R_{0}$. At this point, $I_{0}$ returns $true$ and execution jumps to $I_{5}$, which returns $false$, allowing execution to flow to $I_{6}$. At this point, we need to copy the value of $R_{1}$ (which is now our answer) into $R_{0}$. $I_{6}$ increments $R_{2}$ by one, which acts as a flag, showing that the answer has been computed and is now to be moved into $R_{0}$. $I_{7}$ increments $R_{0}$ (which is now zero) by one. $I_{8}$ decrements $R_{1}$ by one. $I_{9}$ checks if $R_{1}$ is zero. If it is, then the answer has been moved to $R_{0}$ and execution jumps to $I_{11}$, which brings us to a halt. If $R_{1}$ is not zero, execution flows to $I_{10}$ which checks if $R_{3}$ is zero. It will be because we haven't used it, therefore it returns $true$ and executon continues from $I_{6}$ until $R_{0}$ holds the answer of the computation.

\section{Determine the function U$^{(2)}$ computed by the following URM program U:}
\begin{quote}
$I_{0} = iszero(0,4)$\newline
$I_{1} = pred(0)$\newline
$I_{2} = succ(1)$\newline
$I_{3} = iszero(2,0)$\newline
$I_{4} = iszero(1,8)$\newline
$I_{5} = pred(1)$\newline
$I_{6} = succ(0)$\newline
$I_{7} = iszero(2,4)$\newline
\end{quote}

$U^{(2)} = f(a,b) \rightarrow a + b$.

\subsection{Justify your answer. What happens if one omits $I_{4} - I_{7}$ from the program?}

If both starting inputs, $R_{0}$ and $R_{1}$, are zero, then $I_{0}$ returns $true$ and execution jumps to $I_{4}$, which also returns $true$, jumping to $I_{8}$ and ending execution.

If $R_{0} = 0$ and $R_{1} > 0$, $I_{0}$ returns $true$ and execution jumps to $I_{4}$ which returns $false$ and execution carries on to $I_{5}$, which decrements $R_{1}$ by one. $I_{6}$ increments $R_{0}$ by one. $I_{7}$ checks if $R_{2}$ is zero, which it isn't because it hasn't been used. Execution returns to $I_{4}$ and the loop continues until the value in $R_{1}$ is in $R_{0}$. At this point $I_{4}$ returns $true$ and execution ends by jumping to $I_{8}$ leaving the value of $R_{1} + 0$ in $R_{0}$.

If $R_{0} > 0$ and $R_{1} = 0$, $I_{0}$ returns $false$ and the answer is computed in the same way as before, only using instructions $I_{0} - I_{3}$ until the answer is in $R_{1}$. The answer is then moved to $R_{0}$ as before.

The execution where $R_{0} > 0$ and $R_{1} > 0$ proceeds in a simlar fashion to the previous two cases.

If $I_{4} - I_{7}$ are omitted, $U^{(2)} = f(a,b) \rightarrow 0$. This is because the value computed into $R_{1}$ is never moved back to $R_{0}$.

\section{Write a Java program which simulates a URM.}

\begin{quote}
\include{URM.java}
\end{quote}

\section{The programming language Agda has a termination checker, which checks whether the given program is guaranteed to terminate. Prove that we cannot write a perfect termination checker which accepts all terminating programs.}

This was originally proved by Alan Turing and employs diagonalisation and proof by contradiction. Informally, the proof is as follows.
\begin{quote}
Suppose there is an algorithm, $halts(a,i)$, which takes an algorithm, $a$, and an input, $i$. If the algorithm halts on the given input, then $halts(a,i)$ returns $true$.

We then construct an algorithm, $test(s)$, which takes a string, $s$, and runs the $halts$ algorithm as a subroutine, giving it $s$ for both the $a$ and $i$ inputs. If $halts$ returns $true$ then $test$ returns $false$ else goes into an infinite loop.

We then run $test(t)$ where $t$ is the string representing the program $test$.

If $test(t)$ halts, we can assume that $halts$ returned $false$, but this would imply that $test(t)$ should not have halted.

If $test(t)$ does not halt, then it would imply that either $halts$ returned $true$, or that $halts$ itself went into an infinite loop. Therefore, $test(t)$ should have halted or $halt$ does not work for all inputs.

\end{quote}

Turing's proof assumes the algorithms are implemented on a Turing Machine. The Church-Turing thesis proved that any computer which can feasibly be built is equivalent to a Turing Machine, thus all Turing Machines are Universal Machines.

\end{document}