Paper/document/root.tex
changeset 233 e0a7ee9842d6
parent 202 7cfc83879fc9
child 236 6b6d71d14e75
--- 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.}