GNU Make Turing machine simulator

turing.mk

# 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))))