A machine that reads a machine.

The input describes a Turing machine M and the word w you want it to process. Enter the machine’s seven-tuple, followed by a comma and the word:

(Q, Σ, Γ, δ, q0, qaccept, qreject),w

• Q: the finite set of states, such as {q0,q1,qa,qr}.
• Σ (Sigma): the input alphabet, such as {0,1}. It excludes the blank symbol.
• Γ (Gamma): the tape alphabet, such as {0,1,_}. It includes the input alphabet, the blank symbol, and any working symbols.
• δ (delta): the transition function, entered here as a set of input–output pairs.
• q0: the start state.
• qaccept: the accept state, named qa in the example.
• qreject: the reject state, named qr in the example.

Reading a transition

Sipser’s transition function has the form δ: Q × Γ → Q × Γ × {L,R}. It takes a state and a tape symbol and returns a new state, a symbol to write, and a direction.

δ(q0,1) = (q1,1,R)

This means: while in state q0, if the head reads 1, enter q1, write 1, and move one cell right.

In this textbox, write the same rule as:

((q0,1),(q1,1,R))

The outer ordered pair contains an input pair (q0,1) and an output triple (q1,1,R). The surrounding braces collect all these rules into a set. This nested-pair syntax is the application’s text encoding of the function; Sipser’s Section 3.1, Definition 3.3 supplies the mathematical transition-function definition.

Blank symbols and the input word

_ means a blank tape symbol, not a space character. It is an easy-to-type substitute for Sipser’s ⊔. For example, ((q0,_),(qr,_,R)) means: in state q0, read a blank, write a blank, move right, and enter qr.

Write only the word after the tuple, for example ...,q0,qa,qr),11011. The remaining tape cells are automatically blank; do not append blank markers. Use eps for the empty word. Spaces and line breaks in the description are formatting, not tape symbols.

The example machine accepts binary strings ending in 1, so 11011 is accepted. Changing the word to 11010 produces rejection.