Skip to content

Instantly share code, notes, and snippets.

@lava
Last active October 14, 2019 16:30
Show Gist options
  • Save lava/34ff5a1fa28503904aff0e147cebf566 to your computer and use it in GitHub Desktop.
Save lava/34ff5a1fa28503904aff0e147cebf566 to your computer and use it in GitHub Desktop.
GNU Make Turing machine simulator
# A turing machine simulator implemented in pure GNU Make.
# (written for HackoverCTF 2018 organised by cyclopropenylidene)
blank =
space = $(blank) $(blank)
ascii-expand = \
$(subst .,. ,\
$(subst _,_ ,\
$(subst 1,1 ,\
$(subst 0,0 ,\
$(subst A,A ,\
$(subst B,B ,\
$(subst C,C ,\
$(subst D,D ,\
$(subst E,E ,\
$(subst F,F ,\
$(subst H,H ,\
$(subst L,L ,\
$(subst N,N ,\
$(subst R,R ,\
$(subst S,S ,\
$(subst T,T ,\
$(subst a,a ,\
$(subst b,b ,\
$(subst c,c ,\
$(subst u,u ,\
$(subst v,v ,\
$(subst x,x ,\
$(1)))))))))))))))))))))))
# update_position(cmd, position)
update_position = $(or \
$(if $(filter R,$(strip $(1))),$(2) x),\
$(if $(filter L,$(strip $(1))),$(wordlist 2,$(words $(2)),$(2))),\
$(if $(filter N,$(strip $(1))),$(2)))
# ,$(error Invalid head movement))
# extend_tape(position, tape)
# Uses the fact that we can be at most one step out of bounds
extend_tape = \
$(if $(word 1,$(1)),\
$(if $(word $(words $(1)),$(2)),$(2),$(2) 0),\
0 $(2))
# is_halting_state(state)
is_halting_state = $(filter H,$(strip $(1)))
# retrieve_rule(state, symbol, program)
retrieve_rule = $(call ascii-expand,$(filter $(strip $(1))$(strip $(2))%,$(3)))
# next_state(rule)
next_state = $(word 5,$(1))
# next_position(rule, position)
next_position = $(call update_position,$(word 4,$(1)), $(2))
# next_position_ceil(rule, position)
# This is a little bit of a hack, we rely on the fact that if we reached position zero we
# inserted an additional zero to the left, so we're at position one on the new tape.
next_position_ceil = $(or $(call next_position,$(1),$(2)),x)
# next_tape(rule, position, tape)
next_tape = \
$(wordlist 1,$(words $(wordlist 2,$(words $(2)),$(2))),$(3)) \
$(word 3,$(1)) \
$(wordlist $(words $(2) _),$(words $(3)),$(3))
# get_symbol(position, tape)
get_symbol = $(word $(words $(1)), $(2))
# _turing_step(rule, state, position, tape, program)
# Helper to capture the computed value of rule
_turing_step = $(if $(debug),$(info -> applying rule $(1)))\
$(call turing_step,\
$(call next_state, $(1)),\
$(call next_position_ceil, $(1), $(3)),\
$(call extend_tape,\
$(call next_position, $(1), $(3)),\
$(call next_tape, $(1), $(3), $(4))),\
$(5))
# turing_step(state, position, tape, program)
turing_step = $(if $(debug),$(info State $(1) at pos $(words $(2)) w/ tape $(strip $(3)))) $(if $(word 25,$(2)),$(error bound reached)) $(if $(call is_halting_state,$(1)),\
$(3), \
$(call _turing_step,\
$(call retrieve_rule, $(1), $(call get_symbol,$(2),$(3)),$(4)),\
$(1),\
$(2),\
$(3),\
$(4)))
initial_tape = 0
initial_position = x # unary 1-based idx
# Each instruction is encoded as series of 5-tuples
# 1) current state
# 2) symbol at head position
# 3) output symbol
# 4) head movement
# 5) next state
# A program that writes 'uv' and halts
#initial_state = S
#program = S0uRT T0vNH
# A BB(2) machine printing 4 characters
# (need to modify initial position since it wants to go to the left)
#initial_state = a
#program = a01Rb a11Lb b01La b11RH
# A BB(3) machine printing 6 characters
initial_state = a
program = a01Rb a11RH b00Rc b11Rb c01Lc c11La
# A BB(4) machine printing 13 characters
#initial_state = A
#program = A01RB A11LB B01LA B10LC C01RH C11LD D01RD D10RA
# Current BB(5) world record holder, writing 4098 characters
# todo...
# Current BB(6) world record holder, writing MANY characters
# todo..
# Marxen/Buntrock 6-state machine w/ 2,537,699,363,594,175,843,063 ones
#initial_state = A
#program =
# Almost machine 'k' from https://www.drb.insel.de/~heiner/BB/bb-6list
# Slightly modified to print one additional '1'
#initial_state = A
#program = A01RB A10RC \
B00LA B10RD \
C01RD C11RG \
D01LE D10LD \
E01RF E11LB \
F01RA F11RE \
G01RH G11LG
$(info Tape content after program execution: \
$(strip $(call turing_step,\
$(initial_state),\
$(initial_position),\
$(initial_tape),\
$(program))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment