;; Universal Turing Machine Simulation

;; A wax feature demo

​

; enums for shift directions

(@define STAY  0)

(@define LEFT  1)

(@define RIGHT 2)

​

; datastructure for the transition function

(struct transition

    (let q_curr int) ; current state

    (let q_targ int) ; target state

    (let sym_r  int) ; read symbol

    (let sym_w  int) ; write symbol

    (let shift  int) ; shift direction

)

​

; datastructure for the turing machine

; (map int int) is used to represent the tape,

; mapping position to symbol, to simulate "infinite" length.

; tmin/tmax are tape extremas for visualization

(struct machine

    (let state int) ; current state

    (let head  int)

    (let tape  (map int int))

    (let tmin  int) ; leftmost  visited tape position

    (let tmax  int) ; rightmost visited tape position

)

​

; simulate the turing machine for 1 step.

(func step

    (param M (struct machine))

    (param D (arr (struct transition)))

    (let tape (map int int) (get M tape))

​

    ; check each transition function, to see if conditions apply

    (for i 0 (< i (# D)) 1 (do

​

        (if (&&

            (= (get M state)           (get D i q_curr))

            (= (get tape (get M head)) (get D i sym_r ))

        ) (then

            ; execute the transition

            (set tape  (get M head) (get D i sym_w ))

            (set M state            (get D i q_targ))

            (if (= (get D i shift) @LEFT) (then

                (set M head (- (get M head) 1))

            )(else(if (= (get D i shift) @RIGHT) (then

                (set M head (+ (get M head) 1))

            ))))

            (break)

        ))

    ))

​