The Wolfram Atlas of Simple Programs The Wolfram Atlas of Simple Programs

System Categories Cellular Automata Turing Machines Mobile Automata Substitution Systems Tag Systems Register Machines Symbolic Systems Systems Based on Numbers Network Systems Multiway Systems Systems Based on Constraints Axiom Systems
Turing Machines > One-dimensional > 

2-state, 2-color Turing Machines

Machine 1507 - Computational properties on one-sided tapes

Function computed See this image for all rules

Underlying data Magnify image
This machine shows in some ways the most complicated behavior of any 2-color, 2-state Turing machine (A New Kind of Science, page 1144).

Function computed (linear plot) See this image for all rules

Underlying data Magnify image

Halting times See this image for all rules

Underlying data Magnify image Mathematica program
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 Mathematica 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.