86 lines
2.7 KiB
Plaintext
86 lines
2.7 KiB
Plaintext
import Base.show
|
|
|
|
@enum Move Left=1 Stay Right
|
|
|
|
mutable struct MachineState
|
|
state::String
|
|
tape::Dict{Int, String}
|
|
headpos::Int
|
|
end
|
|
|
|
struct Rule
|
|
instate::String
|
|
s1::String
|
|
s2::String
|
|
move::Move
|
|
outstate::String
|
|
end
|
|
|
|
struct Program
|
|
title::String
|
|
initial::String
|
|
final::String
|
|
blank::String
|
|
rules::Vector{Rule}
|
|
end
|
|
|
|
const testprograms = [
|
|
(Program("Simple incrementer", "q0", "qf", "B",
|
|
[Rule("q0", "1", "1", Right, "q0"), Rule("q0", "B", "1", Stay, "qf")]),
|
|
Dict(1 =>"1", 2 => "1", 3 => "1"), true),
|
|
(Program("Three-state busy beaver", "a", "halt", "0",
|
|
[Rule("a", "0", "1", Right, "b"), Rule("a", "1", "1", Left, "c"),
|
|
Rule("b", "0", "1", Left, "a"), Rule("b", "1", "1", Right, "b"),
|
|
Rule("c", "0", "1", Left, "b"), Rule("c", "1", "1", Stay, "halt")]),
|
|
Dict(), true),
|
|
(Program("Five-state busy beaver", "A", "H", "0",
|
|
[Rule("A", "0", "1", Right, "B"), Rule("A", "1", "1", Left, "C"),
|
|
Rule("B", "0", "1", Right, "C"), Rule("B", "1", "1", Right, "B"),
|
|
Rule("C", "0", "1", Right, "D"), Rule("C", "1", "0", Left, "E"),
|
|
Rule("D", "0", "1", Left, "A"), Rule("D", "1", "1", Left, "D"),
|
|
Rule("E", "0", "1", Stay, "H"), Rule("E", "1", "0", Left, "A")]),
|
|
Dict(), false)]
|
|
|
|
function show(io::IO, mstate::MachineState)
|
|
ibracket(i, curpos, val) = (i == curpos) ? "[$val]" : " $val "
|
|
print(io, rpad("($(mstate.state))", 12))
|
|
for i in sort(collect(keys(mstate.tape)))
|
|
print(io, " $(ibracket(i, mstate.headpos, mstate.tape[i]))")
|
|
end
|
|
end
|
|
|
|
function turing(program, tape, verbose)
|
|
println("\n$(program.title)")
|
|
verbose && println(" State \tTape [head]\n--------------------------------------------------")
|
|
mstate = MachineState(program.initial, tape, 1)
|
|
stepcount = 0
|
|
while true
|
|
if !haskey(mstate.tape, mstate.headpos)
|
|
mstate.tape[mstate.headpos] = program.blank
|
|
end
|
|
verbose && println(mstate)
|
|
for rule in program.rules
|
|
if rule.instate == mstate.state && rule.s1 == mstate.tape[mstate.headpos]
|
|
mstate.tape[mstate.headpos] = rule.s2
|
|
if rule.move == Left
|
|
mstate.headpos -= 1
|
|
elseif rule.move == Right
|
|
mstate.headpos += 1
|
|
end
|
|
mstate.state = rule.outstate
|
|
break
|
|
end
|
|
end
|
|
stepcount += 1
|
|
if mstate.state == program.final
|
|
break
|
|
end
|
|
end
|
|
verbose && println(mstate)
|
|
println("Total steps: $stepcount")
|
|
end
|
|
|
|
for (prog, tape, verbose) in testprograms
|
|
turing(prog, tape, verbose)
|
|
end
|