Skip to content

Instantly share code, notes, and snippets.

@ytaki0801
Created January 2, 2023 19:33
Show Gist options
  • Save ytaki0801/e02faba82a5ac680870543331de97d20 to your computer and use it in GitHub Desktop.
Save ytaki0801/e02faba82a5ac680870543331de97d20 to your computer and use it in GitHub Desktop.
2-state 3-symbol State Machine with Two Stacks, same as Wolfram's (2,3) Universal Turing Machine
from time import sleep
# (state,symbol) => (state,symbol,head)
delta = {(0,0):(1,1,+1), (0,1):(0,2,-1), (0,2):(0,1,-1),
(1,0):(0,2,-1), (1,1):(1,2,+1), (1,2):(0,0,+1)}
ds = {0: ' ', 1: '.', 2: '*'}
tlen = 80
state, stack, stackT, head = 0, [0] * tlen, [], int(tlen / 2) - 10
while 0 <= head <= tlen:
for _ in range(head): stackT.insert(0, stack[0]); stack = stack[1:]
state, symbol, headN = delta[(state,stack[0])]
stack = stack[1:]; stack.insert(0, symbol)
for _ in range(head): stack.insert(0, stackT[0]); stackT = stackT[1:]
head += headN
for s in stack: print(ds[s], end='')
print()
sleep(0.005)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment