updated paper
authorChristian Urban <christian dot urban at kcl dot ac dot uk>
Thu, 07 Feb 2013 03:33:32 +0000
changeset 149 199cf7ce1169
parent 148 6ffd6880dad7
child 150 3c504ca0ce95
updated paper
Paper/Paper.thy
--- a/Paper/Paper.thy	Thu Feb 07 03:19:36 2013 +0000
+++ b/Paper/Paper.thy	Thu Feb 07 03:33:32 2013 +0000
@@ -1367,7 +1367,13 @@
   @{thm (concl) UTM_unhalt_lemma2} 
   \end{center}
 
-  \noindent
+  Analysing the universal Turing machine constructed in \cite{Boolos87} more carefully
+  we can strengthen this result slightly by observing that @{text m} is at most
+  2 in the output tape. This observation allows one to construct a UTM that works
+  entirely on the left-tape by composing it with a machine that drags the tape
+  two cells to the right. A corolary is that one-sided Turing machines (where the
+  tape only extends to the right) are as powerful as our two-sided Turing machines. 
+
   While formalising the chapter about universal Turing machines in \cite{Boolos87}
   we noticed that they use their definition about what function Turing machines
   calculate. They write in Chapter 3 \cite[Page 32]{Boolos87}: