Theory: Run any Turing machine

Build a universal simulator: the machine is part of the input.

What to build

A program that runs a Turing machine on several words and reports how each run ends.

Requirements

  • Moves are L, R or S (stay). A missing move rejects.
  • Print accept, reject, or timeout if the machine has not halted after 1000 steps.

Input

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

Output

n lines.

Constraints

At most 20 states, 60 moves and 10 words of at most 20 symbols.

Example

Input:

q0
acc
rej
11
q0 0 q1 X R
q0 Y q3 Y R
q0 _ acc _ R
q1 0 q1 0 R
q1 Y q1 Y R
q1 1 q2 Y L
q2 0 q2 0 L
q2 Y q2 Y L
q2 X q0 X R
q3 Y q3 Y R
q3 _ acc _ R
3
0011
001

Output:

accept
reject
accept

Why it works

A simulator that reads a machine's description and runs it is a universal Turing machine; a step limit is needed because a machine may never halt.

Examples

Example 1 · Input
q0
acc
rej
11
q0 0 q1 X R
q0 Y q3 Y R
q0 _ acc _ R
q1 0 q1 0 R
q1 Y q1 Y R
q1 1 q2 Y L
q2 0 q2 0 L
q2 Y q2 Y L
q2 X q0 X R
q3 Y q3 Y R
q3 _ acc _ R
3
0011
001

Expected output
accept
reject
accept
Example 2 · Input
s
a
r
3
s 0 s 0 R
s 1 s 1 R
s _ s _ R
1
01
Expected output
timeout

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

Hints

Hint 1

Keep the tape in a dictionary; a missing cell holds _.

Hint 2

Stop on the accept or reject state, on a missing move (reject), or after 1000 steps (timeout).

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])


def run(word):
    tape = dict(enumerate(word))
    state, head = start, 0
    for _ in range(1000):
        if state == accept:
            return "accept"
        if state == reject:
            return "reject"
        move = delta.get((state, tape.get(head, "_")))
        if move is None:
            return "reject"
        state, write, step = move
        tape[head] = write
        head += step
    return "accept" if state == accept else "reject" if state == reject else "timeout"


for _ in range(int(input())):
    print(run(input()))

Lesson: Turing machines →