77 lines
2.4 KiB
APL
77 lines
2.4 KiB
APL
:Namespace Turing
|
||
⍝ Run Turing machine until it halts
|
||
∇r←RunTuring (rules init halts blank itape);state;rt;lt;next
|
||
state←init
|
||
lt←⍬
|
||
rt←,blank
|
||
:If 0≠≢itape ⋄ rt←itape ⋄ :EndIf
|
||
:While ~(⊂state)∊halts
|
||
next←((⊂state(⊃rt))≡¨↓rules[;⍳2])⌿rules
|
||
'No rule applies!'⎕SIGNAL(0=≢next)/11
|
||
(⊃rt)←⊃next[1;3]
|
||
state←⊃next[1;5]
|
||
:Select ⊃next[1;4]
|
||
:Case 'stay' ⋄ ⍝nothing
|
||
:Case 'right'
|
||
lt,⍨←⊃rt
|
||
rt←1↓rt
|
||
:If 0=≢rt ⋄ rt←,blank ⋄ :EndIf
|
||
:Case 'left'
|
||
:If 0=≢lt ⋄ lt←,blank ⋄ :EndIf
|
||
rt,⍨←⊃lt
|
||
lt←1↓lt
|
||
:Else
|
||
'Invalid action'⎕SIGNAL 11
|
||
:EndSelect
|
||
:EndWhile
|
||
r←(⌽lt),rt
|
||
∇
|
||
|
||
⍝ Display the resulting tape neatly
|
||
∇r←len Display t
|
||
r←(len⌊≢t)↑t
|
||
→(len≥≢t)/0
|
||
r,←'... (total length: ',(⍕≢t),')'
|
||
∇
|
||
|
||
⍝ Simple incrementer
|
||
∇t←∆1_SimpleIncrementer
|
||
t ←⊂'q0' '1' '1' 'right' 'q0'
|
||
t,←⊂'q0' 'B' '1' 'stay' 'qf'
|
||
t←(↑t) 'q0' (,⊂'qf') 'B' '111'
|
||
∇
|
||
|
||
⍝ Three state beaver
|
||
∇t←∆2_ThreeStateBeaver
|
||
t ←⊂'a' '0' '1' 'right' 'b'
|
||
t,←⊂'a' '1' '1' 'left' 'c'
|
||
t,←⊂'b' '0' '1' 'left' 'a'
|
||
t,←⊂'b' '1' '1' 'right' 'b'
|
||
t,←⊂'c' '0' '1' 'left' 'b'
|
||
t,←⊂'c' '1' '1' 'stay' 'halt'
|
||
t←(↑t) 'a' (,⊂'halt') '0' ''
|
||
∇
|
||
|
||
⍝ Five state beaver
|
||
∇t←∆3_FiveStateBeaver
|
||
t ←⊂'A' '0' '1' 'right' 'B'
|
||
t,←⊂'A' '1' '1' 'left' 'C'
|
||
t,←⊂'B' '0' '1' 'right' 'C'
|
||
t,←⊂'B' '1' '1' 'right' 'B'
|
||
t,←⊂'C' '0' '1' 'right' 'D'
|
||
t,←⊂'C' '1' '0' 'left' 'E'
|
||
t,←⊂'D' '0' '1' 'left' 'A'
|
||
t,←⊂'D' '1' '1' 'left' 'D'
|
||
t,←⊂'E' '0' '1' 'stay' 'H'
|
||
t,←⊂'E' '1' '0' 'left' 'A'
|
||
t←(↑t) 'A' (,⊂'H') '0' ''
|
||
∇
|
||
|
||
⍝ Run all of them and display the results
|
||
∇RunAll;m;ms
|
||
ms←('∆'=⊃¨ms)/ms←⎕NL¯3
|
||
:For m :In ms
|
||
⎕←(1↓m),': ',(32 Display RunTuring ⍎m)
|
||
:EndFor
|
||
∇
|
||
:EndNamespace
|