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, ortimeoutif 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
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
accept reject accept
s a r 3 s 0 s 0 R s 1 s 1 R s _ s _ R 1 01
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()))