equal
deleted
inserted
replaced
1367 @{thm (concl) UTM_unhalt_lemma2} |
1367 @{thm (concl) UTM_unhalt_lemma2} |
1368 \end{center} |
1368 \end{center} |
1369 |
1369 |
1370 Analysing the universal Turing machine constructed in \cite{Boolos87} more carefully |
1370 Analysing the universal Turing machine constructed in \cite{Boolos87} more carefully |
1371 we can strengthen this result slightly by observing that @{text m} is at most |
1371 we can strengthen this result slightly by observing that @{text m} is at most |
1372 2 in the output tape. This observation allows one to construct a UTM that works |
1372 2 in the output tape. This observation allows one to construct a universal Turing machine that works |
1373 entirely on the left-tape by composing it with a machine that drags the tape |
1373 entirely on the left-tape by composing it with a machine that drags the tape |
1374 two cells to the right. A corollary is that one-sided Turing machines (where the |
1374 two cells to the right. A corollary is that one-sided Turing machines (where the |
1375 tape only extends to the right) are computationally as powerful as our two-sided |
1375 tape only extends to the right) are computationally as powerful as our two-sided |
1376 Turing machines. So our undecidability proof for the halting problem extends |
1376 Turing machines. So our undecidability proof for the halting problem extends |
1377 also to one-sided Turing machines, which is needed for example in order to |
1377 also to one-sided Turing machines, which is needed for example in order to |