154 lines
5.1 KiB
Text
154 lines
5.1 KiB
Text
Module CheckIt {
|
|
print "Universal Turing Machine"
|
|
print "------------------------"
|
|
class Machine {
|
|
private:
|
|
Head=1, Symbols=(,), States=(,)
|
|
Initial_State$, Terminating_state$, Blank_Symbol$
|
|
BS=0, Rules=list, caption$
|
|
tp$="{0:4} {1} {2} {3:5} {4:4}"
|
|
public:
|
|
Module States {
|
|
.States<=array([])
|
|
}
|
|
Module Symbols {
|
|
.Symbols<=array([])
|
|
}
|
|
Module Reset (.Initial_State$, .Terminating_state$, .Blank_Symbol$) {
|
|
if len(.States)=0 then error "No States defined"
|
|
if len(.Symbols)=0 then error "No Symbols defined"
|
|
if .States#nothave(.Initial_State$) then error "Initial State Not Exist"
|
|
if .States#nothave(.Terminating_state$) then error "Terminating State Not Exist"
|
|
it=.Symbols#pos(.Blank_Symbol$) : if it=-1 then error "Blank symbol not exist"
|
|
.BS<=it
|
|
.Rules<=List
|
|
}
|
|
Module Init (.caption$) {
|
|
flush // empty stack
|
|
print .caption$
|
|
}
|
|
Module AddRule (state$, read_symbol$, write_symbol$, action$, end_state$) {
|
|
|
|
if .States#nothave(state$) then Error "State not exist"
|
|
if .symbols#nothave(read_symbol$) then Error "Read Symbol not exist"
|
|
if .symbols#nothave(write_symbol$) then Error "Read Symbol not exist"
|
|
if ("right","left","stay")#nothave(action$) then Error "Action not exist"
|
|
if .States#nothave(end_state$) then Error "End state not exist"
|
|
try ok {
|
|
tuple=(.symbols#pos(write_symbol$), action$, end_state$)
|
|
Append .rules, state$+"_"+read_symbol$:=tuple
|
|
}
|
|
if not ok then error "rule "+ state$+"_"+read_symbol$+" already exist "
|
|
Pen 11 {
|
|
Print format$(.tp$, state$, read_symbol$, write_symbol$, action$, end_state$)
|
|
}
|
|
if stack.size>=5 then loop
|
|
}
|
|
Module Tape {
|
|
s=[]
|
|
m=each(s)
|
|
while m
|
|
it= .Symbols#pos(stackitem$(m))
|
|
if it=-1 then error "Tape symbol not exist at position ";m^
|
|
data it
|
|
end while
|
|
}
|
|
Module Run (steps as long, display as boolean) {
|
|
if len(.rules)=0 then error "No rules found"
|
|
if .Initial_State$="" or .Terminating_state$="" or .Blank_Symbol$="" then
|
|
error "Reset the machine please"
|
|
end if
|
|
if empty then push .BS
|
|
curState$=.Initial_State$
|
|
cont=true
|
|
.head<=1
|
|
dim inst$() : link inst$() to inst()
|
|
while curState$<>.Terminating_state$
|
|
if display then pen 15 {showstack()}
|
|
steps--
|
|
theRule$=curState$+"_"+.symbols#val$(stackitem(.head))
|
|
if not exist(.Rules, theRule$) then error "Undefined "+theRule$
|
|
inst$()=.Rules(theRule$)
|
|
shift .head : drop :push inst(0): shiftback .head
|
|
select case inst$(1)
|
|
case "right"
|
|
.head++ : if .head>stack.size then data .BS
|
|
case "left"
|
|
if .head<=1 then push .BS else .head--
|
|
else case
|
|
cont=false
|
|
end select
|
|
// change state
|
|
curState$=inst$(2)
|
|
// Show Stack
|
|
if steps=0 or not cont then exit
|
|
end while
|
|
if steps=0 then print over
|
|
Pen 12 {showstack()}
|
|
print "tape length: ";stack.size : flush
|
|
Refresh
|
|
sub showstack()
|
|
local d$=format$("{0:-5} {1::-5} ", curState$, .head)
|
|
local i: for i=1 to min.data(stack.size, 60): d$+=.symbols#val$(stackitem(i)):Next
|
|
print d$
|
|
end sub
|
|
}
|
|
}
|
|
Turing1=Machine()
|
|
For Turing1 {
|
|
.init "Simple incrementer"
|
|
.States "q0", "qf"
|
|
.Symbols "B", "1"
|
|
.Reset "q0", "qf", "B" // initial state, terminating state, blank symbol
|
|
.AddRule "q0", "1", "1", "right", "q0"
|
|
.AddRule "q0", "B", "1", "stay", "qf"
|
|
.tape "1", "1", "1"
|
|
.Run 100, true
|
|
}
|
|
Turing2=Machine()
|
|
For Turing2 {
|
|
.init "Three-state busy beaver"
|
|
.States "a", "b", "c", "halt"
|
|
.Symbols "0", "1"
|
|
.Reset "a", "halt", "0"
|
|
.AddRule "a", "0", "1", "right", "b", "a", "1", "1", "left", "c"
|
|
.AddRule "b", "0", "1", "left", "a", "b", "1", "1", "right", "b"
|
|
.AddRule "c", "0", "1", "left", "b", "c", "1", "1", "stay", "halt"
|
|
.Run 1000, true
|
|
}
|
|
|
|
For Turing1 {
|
|
.init "Sorter"
|
|
.States "A","B","C","D","E","X"
|
|
.Symbols "a","b","B","*"
|
|
.Reset "A", "X", "*"
|
|
.AddRule "A", "a", "a", "right", "A", "A", "b", "B", "right", "B"
|
|
.AddRule "A", "*", "*", "left", "E", "B", "a", "a", "right", "B"
|
|
.AddRule "B", "b", "b", "right", "B", "B", "*", "*", "left", "C"
|
|
.AddRule "C", "a", "b", "left", "D", "C", "b", "b", "left", "C"
|
|
.AddRule "C", "B", "b", "left", "E", "D", "a", "a", "left", "D"
|
|
.AddRule "D", "b", "b", "left", "D", "D", "B", "a", "right", "A"
|
|
.AddRule "E", "a", "a", "left", "E", "E", "*", "*", "right", "X"
|
|
.tape "b", "a", "b","b","b","a","a"
|
|
.Run 100, false
|
|
}
|
|
Turing1.tape "b","b","b","a","b","a","b","a","a","a","b","b","a"
|
|
Turing1.Run 1000, false
|
|
|
|
Turing3=Machine()
|
|
for Turing3 {
|
|
.init "5-state, 2-symbol probable Busy Beaver machine from Wikipedia"
|
|
.States "A","B","C","D", "E", "H"
|
|
.Symbols "0", "1"
|
|
.Reset "A", "H", "0"
|
|
.AddRule "A", "0", "1", "right", "B", "A", "1", "1", "left", "C"
|
|
.AddRule "B", "0", "1", "right", "C", "B", "1", "1", "right", "B"
|
|
.AddRule "C", "0", "1", "right", "D", "C", "1", "1", "left", "E"
|
|
.AddRule "D", "0", "1", "left", "A", "D", "1", "1", "left", "D"
|
|
.AddRule "E", "0", "1", "stay", "H", "E", "1", "0", "left", "A"
|
|
profiler
|
|
.Run 470, false //000000, false
|
|
Print round(timecount/1000,2);"s" // estimated 12.5 hours for 47000000 steps
|
|
}
|
|
}
|
|
CheckIt
|