| I got bored during a theory class, and wanted to write some Arc code to help me learn the language. Decided on this little project: a macro that, when given a description of a turing machine, returns a function that simulates that turing machine. Give that function an input tape and it will return the tape after the turing machine halts. It adds extra blank characters to the end or beginning of the list representing the tape as needed, so it can simulate an "infinite" tape. Apologies to the Lisp experienced, as I'm just learning the ropes. Here's the code, written for arc1: ;turing.arc
;Stefan J. Wernli 2/12/08
;Turing machine creator
;Arguments:
; transition table as list of state-input pairs with
; newstate-output-tapemove,
; eg: ((state1 input) '(state2 output {r|l|n}))
; blank symbol
; start state
; list of end states
; optional list of error states
;Returns:
; function that when given a tape (list of inputs) will run specified
; turing machine and return final tape
; simulates as 1-tape left and right infinite turing machine
; if given no arguments, assumes infinite blank tape
(mac turing (tfunclist blank start end (o er))
(let tfunc `(obj ,@tfunclist)
`(fn ((o tape nil)) (if (no tape) (= tape `(,,blank)))
((rfn tstep (i state)
(let result (,tfunc (eval `'(,state ,tape.i)))
(if (some [is _ state] ,er)
(err "Reached error state" `(,state) 'on 'tape tape)
(some [is _ state] ,end)
tape
(do (if (no result)
(err "Rule error: no rule for input"
`(,tape.i) 'at 'state `(,state)))
(if (~no result.1) (= tape.i result.1))
(tstep
(let newi (+ i ((fn (x) (case x r 1 l -1 n 0))
result.2))
(if (is newi (len tape))
(do (= tape `(,@tape ,,blank)) newi)
(< newi 0) (do (= tape `(,,blank ,@tape)) 0)
newi)) result.0))))) 0 ,start))))
;test
((turing
((st1 ())'(st3 () n)(st1 a)'(st1 () r)(st1 b)'(st2 () n)) ;transition table
nil ;blank
'st1 ;start state
'(st2) ;list of end states
'(st3)) ;list of error states
'(a a b)) ;input list
;example
(= busy-beaver
(turing
((a 0)'(b 1 r)
(a 1)'(c 1 l)
(b 0)'(a 1 l)
(b 1)'(b 1 r)
(c 0)'(b 1 l)
(c 1)'(halt 1 n)) ;transition table
0 ;blank
'a ;start state
'(halt))) ;list of end states
|
