

Machine 1507  Computational properties on onesided tapes 

 Function computed 





This machine shows in some ways the most complicated behavior of any 2color, 2state Turing machine (A New Kind of Science, page 1144). 
 Function computed (linear plot) 


 Halting times 





The halting problem for this Turing machine is decidable. The machine halts if and only if it is never in state 1 on the leftmost black cell when the right neighbor of that cell is also black. This program determines whether the the machine will ever halt, using at most steps even though the original machine can take of order steps to halt. 
Previous section

© Wolfram Research, Inc.
