Paper/Paper.thy
changeset 134 f47f1ef313d1
parent 133 ca7fb6848715
child 135 ba63ba7d282b
equal deleted inserted replaced
133:ca7fb6848715 134:f47f1ef313d1
  1324   with the standard tape @{term "([Bk, Bk], <ns::nat list>)"} will terminate
  1324   with the standard tape @{term "([Bk, Bk], <ns::nat list>)"} will terminate
  1325   with the standard tape @{term "(Bk \<up> k, <n::nat> @ Bk \<up> l)"} for some @{text k} and @{text l}.
  1325   with the standard tape @{term "(Bk \<up> k, <n::nat> @ Bk \<up> l)"} for some @{text k} and @{text l}.
  1326 
  1326 
  1327   and the also the definition of the
  1327   and the also the definition of the
  1328   universal function (we refer the reader to our formalisation).
  1328   universal function (we refer the reader to our formalisation).
       
  1329 
       
  1330   \cite[Page 32]{Boolos87}
       
  1331 
       
  1332   \begin{quote}\it
       
  1333   ``If the function that is to be computed assigns no value to the arguments that 
       
  1334   are represented initially on the tape, then the machine either will never halt, 
       
  1335   or will halt in some nonstandard configuration\ldots''
       
  1336   \end{quote}
  1329   
  1337   
       
  1338   This means that if you encode the plus function but only give one argument,
       
  1339   then the TM will either loop {\bf or} stop with a non-standard tape
       
  1340 
       
  1341   But in the definition of the universal function the TMs will never stop
       
  1342   with non-standard tapes. 
       
  1343 
       
  1344   SO the following TM calculates something according to def from chap 8,
       
  1345   but not with chap 3. For example:
       
  1346   
       
  1347   \begin{center}
       
  1348   @{term "[(L, 0), (L, 2), (R, 2), (R, 0)]"}
       
  1349   \end{center}
       
  1350 
       
  1351   If started with @{term "([], [Oc])"} it halts with the
       
  1352   non-standard tape @{term "([Oc], [])"} according to the definition in Chap 3;
       
  1353   but with @{term "([], [Oc])"} according to def Chap 8
       
  1354 
  1330 *}
  1355 *}
  1331 
  1356 
  1332 (*
  1357 (*
  1333 section {* Wang Tiles\label{Wang} *}
  1358 section {* Wang Tiles\label{Wang} *}
  1334 
  1359