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 |