85 lines
2.6 KiB
Lua
85 lines
2.6 KiB
Lua
-- Machine definitions
|
|
local incrementer = {
|
|
name = "Simple incrementer",
|
|
initState = "q0",
|
|
endState = "qf",
|
|
blank = "B",
|
|
rules = {
|
|
{"q0", "1", "1", "right", "q0"},
|
|
{"q0", "B", "1", "stay", "qf"}
|
|
}
|
|
}
|
|
|
|
local 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"}
|
|
}
|
|
}
|
|
|
|
local 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"}
|
|
}
|
|
}
|
|
|
|
-- Display a representation of the tape and machine state on the screen
|
|
function show (state, headPos, tape)
|
|
local leftEdge = 1
|
|
while tape[leftEdge - 1] do leftEdge = leftEdge - 1 end
|
|
io.write(" " .. state .. "\t| ")
|
|
for pos = leftEdge, #tape do
|
|
if pos == headPos then io.write("[" .. tape[pos] .. "] ") else io.write(" " .. tape[pos] .. " ") end
|
|
end
|
|
print()
|
|
end
|
|
|
|
-- Simulate a turing machine
|
|
function UTM (machine, tape, countOnly)
|
|
local state, headPos, counter = machine.initState, 1, 0
|
|
print("\n\n" .. machine.name)
|
|
print(string.rep("=", #machine.name) .. "\n")
|
|
if not countOnly then print(" State", "| Tape [head]\n---------------------") end
|
|
repeat
|
|
if not tape[headPos] then tape[headPos] = machine.blank end
|
|
if not countOnly then show(state, headPos, tape) end
|
|
for _, rule in ipairs(machine.rules) do
|
|
if rule[1] == state and rule[2] == tape[headPos] then
|
|
tape[headPos] = rule[3]
|
|
if rule[4] == "left" then headPos = headPos - 1 end
|
|
if rule[4] == "right" then headPos = headPos + 1 end
|
|
state = rule[5]
|
|
break
|
|
end
|
|
end
|
|
counter = counter + 1
|
|
until state == machine.endState
|
|
if countOnly then print("Steps taken: " .. counter) else show(state, headPos, tape) end
|
|
end
|
|
|
|
-- Main procedure
|
|
UTM(incrementer, {"1", "1", "1"})
|
|
UTM(threeStateBB, {})
|
|
UTM(fiveStateBB, {}, "countOnly")
|