diff -r 904f9351ab94 -r c67e8ed4c865 Paper/Paper.thy --- a/Paper/Paper.thy Sun Jan 27 00:09:17 2013 +0000 +++ b/Paper/Paper.thy Sun Jan 27 14:57:54 2013 +0000 @@ -183,8 +183,8 @@ our formalisation we follow mainly the proofs from the textbook \cite{Boolos87} and found that the description there is quite detailed. Some details are left out however: for example, constructing -the \emph{copy Turing program} is left as an excerise; also the -book only shows how the universal Turing machine is constructed for Turing +the \emph{copy Turing program} is left as an excerise to the reader; also +\cite{Boolos87} only shows how the universal Turing machine is constructed for Turing machines computing unary functions. We had to figure out a way to generalise this result to $n$-ary functions. Similarly, when compiling recursive functions to abacus machines, the textbook again only shows @@ -259,7 +259,7 @@ the head and @{term r} for the tape on the right-hand side. We use the notation @{term "Bk \ n"} (similarly @{term "Oc \ n"}) for lists composed of @{term n} elements of @{term Bk}s. We also have the - convention that the head, abbreviated @{term hd}, of the right-list + convention that the head, abbreviated @{term hd}, of the right list is the cell on which the head of the Turing machine currently scannes. This can be pictured as follows: % @@ -329,20 +329,20 @@ \end{center} \noindent - The first two clauses replace the head of the right-list + The first two clauses replace the head of the right list with a new @{term Bk} or @{term Oc}, respectively. To see that these two clauses make sense in case where @{text r} is the empty list, one has to know that the tail function, @{term tl}, is defined such that @{term "tl [] == []"} holds. The third clause implements the move of the head one step to the left: we need to test if the left-list @{term l} is empty; if yes, then we just prepend a - blank cell to the right-list; otherwise we have to remove the - head from the left-list and prepend it to the right-list. Similarly + blank cell to the right list; otherwise we have to remove the + head from the left-list and prepend it to the right list. Similarly in the fourth clause for a right move action. The @{term Nop} operation leaves the the tape unchanged. %Note that our treatment of the tape is rather ``unsymmetric''---we - %have the convention that the head of the right-list is where the + %have the convention that the head of the right list is where the %head is currently positioned. Asperti and Ricciotti %\cite{AspertiRicciotti12} also considered such a representation, but %dismiss it as it complicates their definition for \emph{tape @@ -629,10 +629,10 @@ \end{tikzpicture}\\[-8mm]\mbox{} \end{center} \caption{The components of the \emph{copy Turing machine} (above). If started - with the tape @{term "([], <[(2::nat)]>)"} the first machine adds @{term "[Bk, Oc]"} at + with the tape @{term "([], <[2::nat]>)"} the first machine appends @{term "[Bk, Oc]"} at the end of the right tape; the second then ``moves'' all @{term Oc}s except the first from the beginning of the tape to the end; the third ``refills'' the original - block of @{term "Oc"}s. The result is the tape @{term "([Bk], <[(2::nat, 2::nat)]>)"}.} + block of @{term "Oc"}s. The resulting tape is @{term "([Bk], <[2::nat, 2::nat]>)"}.} \label{copy} \end{figure}