The input is a binary string consisting of 0s and 1s which encodes a Turing Machine (TM) . Initially, the head of the machine is positioned at the leftmost character of the word . In this context, the word is clearly separated from the TM by a triplet of 1s (111) and is processed without undergoing any form of encoding.
For example, a transition in the TM represented as is encoded in the binary format 0100100010100. The word , on the other hand, remains in its original, un-encoded form. For example, 00ab would be represented directly as 00ab. Thus, the complete input string is formulated as or 010010001010011100ab, where denotes the concatenation operator.
This document describes the coding scheme for the Turing machine , formally expressed as . Note that must always be the initial state, and is the only accepting state.
Make sure that the TM has an initial and final state. Where q1 is the initial state and q2 is the final state.
You can debug your TM by checking the interpreted transition table or by visualizing the TM as a graph. If the TM halted in a rejected state, the state in which it halted will be highlighted in the graph.