diff -r 5317c92ff2a7 -r bd320b5365e2 Paper/Paper.thy --- a/Paper/Paper.thy Tue Jan 29 13:00:51 2013 +0000 +++ b/Paper/Paper.thy Tue Jan 29 16:37:38 2013 +0000 @@ -719,13 +719,13 @@ with total correctness and non-terminantion, rather than have notions for partial correctness and termination. Although the latter would allow us to reason more uniformly (only using Hoare-triples), - we prefer our definitions because we can derive simple + we prefer our definitions because we can derive below some simple Hoare-rules for sequentially composed Turing programs. In this way we can reason about the correctness of @{term "tcopy_begin"}, for example, completely separately from @{term "tcopy_loop"} and @{term "tcopy_end"}. - It is realatively straightforward to prove that the Turing program + It is realatively straightforward to prove that the small Turing program @{term "dither"} shown in \eqref{dither} is correct. This program should be the ``identity'' when started with a standard tape representing @{text "1"} but loop when started with @{text 0} instead, as pictured @@ -795,12 +795,13 @@ The first is by a simple calculation. The second is by induction on the number of steps we can perform starting from the input tape. - The purpose of the @{term tcopy} program defined in \eqref{tcopy} is - to produce the standard tape @{term "(DUMMY, <[n, n::nat]>)"} when - started with @{term "(DUMMY, <[n::nat]>)"}, that is making a copy of - a value on the tape. Reasoning about this program is substantially - harder than about @{term dither}. To ease the burden, we prove - the following two Hoare-rules for sequentially composed programs. + The program @{term tcopy} defined in \eqref{tcopy} has 15 states; + its purpose is to produce the standard tape @{term "(DUMMY, <[n, + n::nat]>)"} when started with @{term "(DUMMY, <[n::nat]>)"}, that is + making a copy of a value on the tape. Reasoning about this program + is substantially harder than about @{term dither}. To ease the + burden, we prove the following two Hoare-rules for sequentially + composed programs. \begin{center} \begin{tabular}{@ {\hspace{-10mm}}c@ {\hspace{14mm}}c@ {}} @@ -827,8 +828,17 @@ The Hoare-rules above allow us to prove the correctness of @{term tcopy} by considering the correctness of @{term "tcopy_begin"}, @{term "tcopy_loop"} - and @{term "tcopy_end"} in isolation. We will show the details for the - the program @{term "tcopy_begin"}. + and @{term "tcopy_end"} in isolation. We will show the details for + the program @{term "tcopy_begin"}. We found the following invariants for each + state: + + \begin{center} + @{thm inv_begin0.simps}\\ + @{thm inv_begin1.simps}\\ + @{thm inv_begin2.simps}\\ + @{thm inv_begin3.simps}\\ + @{thm inv_begin4.simps} + \end{center} measure for the copying TM, which we however omit.