Theory: Watch a Turing machine work

Print every configuration of a Turing machine's run.

What to build

A program that prints each configuration of a machine's run on each word, then the result.

Requirements

  • A configuration line is state: tape, where the tape shows every cell from the leftmost to the rightmost seen so far, and the head's cell is written in brackets, such as q1: X[1].
  • A run ends with accept (accept state), reject (reject state or missing move) or timeout after 200 moves.

Input

Line 1: start state. Line 2: accept state. Line 3: reject state. Line 4: t, then t lines state read next write move (L, R or S). Then n and n words (a word may be an empty line).

Output

For each word, its configurations and then the result.

Constraints

At most 10 states, 30 moves and 5 words of at most 8 symbols.

Example

Input:

f
a
r
3
f 0 f 1 R
f 1 f 0 R
f _ a _ S
1
01

Output:

f: [0]1
f: 1[1]
f: 10[_]
a: 10[_]
accept

Why it works

A configuration (state, tape, head) is the complete situation of the machine; printing each one shows the computation exactly.

Examples

Example 1 · Input
f
a
r
3
f 0 f 1 R
f 1 f 0 R
f _ a _ S
1
01
Expected output
f: [0]1
f: 1[1]
f: 10[_]
a: 10[_]
accept
Example 2 · Input
right
done
fail
4
right 1 right 1 R
right _ carry _ L
carry 1 carry 0 L
carry _ done 1 L
1
1
Expected output
right: [1]
right: 1[_]
carry: [1]_
carry: [_]0_
done: [_]10_
accept

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Track the leftmost and rightmost cells seen so far (input, head positions); print that range with the head's cell in brackets.

Hint 2

Print the starting configuration, then one line after every move; finish with accept or reject.

Solution

Show one correct solution (try it yourself first)
start = input().strip()
accept = input().strip()
reject = input().strip()
delta = {}
for _ in range(int(input())):
    state, read, nxt, write, move = input().split()
    delta[(state, read)] = (nxt, write, {"L": -1, "R": 1, "S": 0}[move])

for _ in range(int(input())):
    word = input()
    tape = dict(enumerate(word))
    state, head = start, 0
    low, high = 0, max(len(word) - 1, 0)

    def show():
        cells = []
        for i in range(low, high + 1):
            symbol = tape.get(i, "_")
            cells.append(f"[{symbol}]" if i == head else symbol)
        print(f"{state}: " + "".join(cells))

    show()
    result = "timeout"
    for _ in range(200):
        if state == accept:
            result = "accept"
            break
        if state == reject:
            result = "reject"
            break
        move = delta.get((state, tape.get(head, "_")))
        if move is None:
            result = "reject"
            break
        state, write, step = move
        tape[head] = write
        head += step
        low, high = min(low, head), max(high, head)
        show()
    else:
        result = "accept" if state == accept else "reject" if state == reject else "timeout"
    print(result)

Lesson: Turing machines →