Skip to content

Instantly share code, notes, and snippets.

@ytaki0801
Created January 3, 2023 04:46
Show Gist options
  • Save ytaki0801/df07d7a082869f42b69fba369f419b9f to your computer and use it in GitHub Desktop.
Save ytaki0801/df07d7a082869f42b69fba369f419b9f to your computer and use it in GitHub Desktop.
2-state 3-symbol State Machine with Two Stacks and One Cell, 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: '*'}
state, stackL, C, stackR = 0, [0]*29, 0, [0]*50
while len(stackL) > 0 and len(stackR) > 0:
state, C, head = delta[(state,C)]
if head == +1:
stackL.insert(0, C)
C = stackR[0]; stackR = stackR[1:]
else:
stackR.insert(0, C)
C = stackL[0]; stackL = stackL[1:]
for s in list(reversed(stackL))+[C]+stackR : 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