Small Turing Machines with Halting State: Enumeration and Running on a Blank Tape
Small Turing Machines with Halting State: Enumeration and Running on a Blank Tape
This Demonstration shows two different enumerations for Turing machines with a halting state, following the formalism of the busy beaver. The complete enumeration contains all possible machines for the given number of states and a binary alphabet. The reduced enumeration contains only those machines with the initial transition moving to the right to a state other than the halting and initial states. The output of the machines removed from the complete enumeration is easily calculated by looking at the transition table and to symmetric machines. The halting executions, starting on a blank tape, are also shown.