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 asq1: X[1]. - A run ends with
accept(accept state),reject(reject state or missing move) ortimeoutafter 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
f a r 3 f 0 f 1 R f 1 f 0 R f _ a _ S 1 01
f: [0]1 f: 1[1] f: 10[_] a: 10[_] accept
right done fail 4 right 1 right 1 R right _ carry _ L carry 1 carry 0 L carry _ done 1 L 1 1
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)