94 lines
2.8 KiB
Plaintext
94 lines
2.8 KiB
Plaintext
enum name, initState, endState, blank, rules
|
|
|
|
-- Machine definitions
|
|
constant incrementer = {
|
|
/*name =*/ "Simple incrementer",
|
|
/*initState =*/ "q0",
|
|
/*endState =*/ "qf",
|
|
/*blank =*/ "B",
|
|
/*rules =*/ {
|
|
{"q0", "1", "1", "right", "q0"},
|
|
{"q0", "B", "1", "stay", "qf"}
|
|
}
|
|
}
|
|
|
|
constant threeStateBB = {
|
|
/*name =*/ "Three-state busy beaver",
|
|
/*initState =*/ "a",
|
|
/*endState =*/ "halt",
|
|
/*blank =*/ "0",
|
|
/*rules =*/ {
|
|
{"a", "0", "1", "right", "b"},
|
|
{"a", "1", "1", "left", "c"},
|
|
{"b", "0", "1", "left", "a"},
|
|
{"b", "1", "1", "right", "b"},
|
|
{"c", "0", "1", "left", "b"},
|
|
{"c", "1", "1", "stay", "halt"}
|
|
}
|
|
}
|
|
|
|
constant fiveStateBB = {
|
|
/*name =*/ "Five-state busy beaver",
|
|
/*initState =*/ "A",
|
|
/*endState =*/ "H",
|
|
/*blank =*/ "0",
|
|
/*rules =*/ {
|
|
{"A", "0", "1", "right", "B"},
|
|
{"A", "1", "1", "left", "C"},
|
|
{"B", "0", "1", "right", "C"},
|
|
{"B", "1", "1", "right", "B"},
|
|
{"C", "0", "1", "right", "D"},
|
|
{"C", "1", "0", "left", "E"},
|
|
{"D", "0", "1", "left", "A"},
|
|
{"D", "1", "1", "left", "D"},
|
|
{"E", "0", "1", "stay", "H"},
|
|
{"E", "1", "0", "left", "A"}
|
|
}
|
|
}
|
|
|
|
procedure show(string state, integer headpos, sequence tape)
|
|
printf(1," %-6s | ",{state})
|
|
for p=1 to length(tape) do
|
|
printf(1,iff(p=headpos?"[%s]":" %s "),{tape[p]})
|
|
end for
|
|
printf(1,"\n")
|
|
end procedure
|
|
|
|
-- a universal turing machine
|
|
procedure UTM(sequence machine, sequence tape, integer countOnly=0)
|
|
string state = machine[initState]
|
|
integer headpos = 1, counter = 0
|
|
printf(1,"\n\n%s\n%s\n",{machine[name],repeat('=',length(machine[name]))})
|
|
if not countOnly then printf(1," State | Tape [head]\n---------------------\n") end if
|
|
while 1 do
|
|
if headpos>length(tape) then
|
|
tape = append(tape,machine[blank])
|
|
elsif headpos<1 then
|
|
tape = prepend(tape,machine[blank])
|
|
headpos = 1
|
|
end if
|
|
if not countOnly then show(state, headpos, tape) end if
|
|
for i=1 to length(machine[rules]) do
|
|
sequence rule = machine[rules][i]
|
|
if rule[1]=state and rule[2]=tape[headpos] then
|
|
tape[headpos] = rule[3]
|
|
if rule[4] == "left" then headpos -= 1 end if
|
|
if rule[4] == "right" then headpos += 1 end if
|
|
state = rule[5]
|
|
exit
|
|
end if
|
|
end for
|
|
counter += 1
|
|
if state=machine[endState] then exit end if
|
|
end while
|
|
if countOnly then
|
|
printf(1,"Steps taken: %d\n",{counter})
|
|
else
|
|
show(state, headPos, tape)
|
|
end if
|
|
end procedure
|
|
|
|
UTM(incrementer, {"1", "1", "1"})
|
|
UTM(threeStateBB, {})
|
|
UTM(fiveStateBB, {}, countOnly:=1)
|