--- a/Paper/document/root.tex Fri Mar 29 01:36:45 2013 +0000
+++ b/Paper/document/root.tex Fri Mar 29 02:40:38 2013 +0000
@@ -50,16 +50,21 @@
\begin{abstract}
We present a formalised theory of computability in the theorem prover
-Isabelle/HOL. This theorem prover is based on classical logic which
-precludes \emph{direct} reasoning about computability: every boolean
-predicate is either true or false because of the law of excluded
-middle. The only way to reason about computability in a classical
-theorem prover is to formalise a concrete model of computation. We
-formalise Turing machines and relate them to abacus machines and
-recursive functions. We also formalise a universal Turing machine and
-Hoare-style reasoning techniques that allow us to reason about Turing machine
-programs. Our theory can be used to formalise other computability
-results. %We give one example about the computational equivalence of
+Isabelle/HOL.
+%This theorem prover is based on classical logic which
+%precludes \emph{direct} reasoning about computability: every boolean
+%predicate is either true or false because of the law of excluded
+%middle. The only way to reason about computability in a classical
+%theorem prover is to formalise a concrete model of computation.
+Following the textbook by Boolos et al, we formalise Turing machines
+and relate them to abacus machines and recursive functions. We ``tie
+the know'' between these three computational models by formalising a
+universal function and obtaining from it a universal Turing machine by
+our verified translation from recursive functions to abacus programs
+and from abacus programs to Turing machine programs. Hoare-style reasoning techniques allow us
+to reason about Turing machine and abacus programs. Our theory can be
+used to formalise other computability results.
+%We give one example about the computational equivalence of
%single-sided Turing machines.
%{\it we give one example about the undecidability of Wang's tiling problem, whose proof uses
%the notion of a universal Turing machine.}