114 lines
2.9 KiB
Plaintext
114 lines
2.9 KiB
Plaintext
// Machine definitions
|
|
|
|
name = 1 : initState = 2 : endState = 3 : blank = 4 : countOnly = true
|
|
|
|
incrementer$ = "Simple incrementer,q0,qf,B"
|
|
incrementer$ = incrementer$ + ",q0,1,1,right,q0,q0,B,1,stay,qf"
|
|
|
|
threeStateBB$ = "Three-state busy beaver,a,halt,0"
|
|
data "a,0,1,right,b"
|
|
data "a,1,1,left,c"
|
|
data "b,0,1,left,a"
|
|
data "b,1,1,right,b"
|
|
data "c,0,1,left,b"
|
|
data "c,1,1,stay,halt"
|
|
data ""
|
|
|
|
do
|
|
read a$
|
|
if a$ = "" break
|
|
threeStateBB$ = threeStateBB$ + "," + a$
|
|
loop
|
|
|
|
|
|
fiveStateBB$ = "Five-state busy beaver,A,H,0"
|
|
data "A,0,1,right,B"
|
|
data "A,1,1,left,C"
|
|
data "B,0,1,right,C"
|
|
data "B,1,1,right,B"
|
|
data "C,0,1,right,D"
|
|
data "C,1,0,left,E"
|
|
data "D,0,1,left,A"
|
|
data "D,1,1,left,D"
|
|
data "E,0,1,stay,H"
|
|
data "E,1,0,left,A"
|
|
data ""
|
|
|
|
do
|
|
read a$
|
|
if a$ = "" break
|
|
fiveStateBB$ = fiveStateBB$ + "," + a$
|
|
loop
|
|
|
|
clear screen
|
|
|
|
// Display a representation of the tape and machine state on the screen
|
|
sub show(state$, headPos, tape$)
|
|
local pos
|
|
|
|
print " ", state$, "\t| ";
|
|
for pos = 1 to len(tape$)
|
|
if pos = headPos then print "[", mid$(tape$, pos, 1), "] "; else print " ", mid$(tape$, pos, 1), " "; end if
|
|
next
|
|
print
|
|
end sub
|
|
|
|
sub string.rep$(s$, n)
|
|
local i, r$
|
|
|
|
for i = 1 to n
|
|
r$ = r$ + s$
|
|
next
|
|
|
|
return r$
|
|
end sub
|
|
|
|
|
|
// Simulate a turing machine
|
|
sub UTM(mach$, tape$, countOnly)
|
|
local state$, headPos, counter, machine$(1), n, m, rule
|
|
|
|
m = len(tape$)
|
|
n = token(mach$, machine$(), ",")
|
|
state$ = machine$(initState)
|
|
n = n - blank
|
|
headPos = 1
|
|
|
|
print "\n\n", machine$(name)
|
|
print string.rep$("=", len(machine$(name))), "\n"
|
|
if not countOnly print " State", "\t| Tape [head]\n----------------------"
|
|
|
|
repeat
|
|
if mid$(tape$, headPos, 1) = " " mid$(tape$, headPos, 1) = machine$(blank)
|
|
if not countOnly show(state$, headPos, tape$)
|
|
for rule = blank + 1 to n step 5
|
|
if machine$(rule) = state$ and machine$(rule + 1) = mid$(tape$, headPos, 1) then
|
|
mid$(tape$, headPos, 1) = machine$(rule + 2)
|
|
if machine$(rule + 3) = "left" then
|
|
headPos = headPos - 1
|
|
if headPos < 1 then
|
|
headPos = 1
|
|
tape$ = " " + tape$
|
|
end if
|
|
end if
|
|
if machine$(rule + 3) = "right" then
|
|
headPos = headPos + 1
|
|
if headPos > m then
|
|
m = m + 1
|
|
tape$ = tape$ + " "
|
|
end if
|
|
end if
|
|
state$ = machine$(rule + 4)
|
|
break
|
|
end if
|
|
next
|
|
counter = counter + 1
|
|
until(state$ = machine$(endState))
|
|
if countOnly then print "Steps taken: ", counter else show(state$, headPos, tape$) end if
|
|
end sub
|
|
|
|
// Main procedure
|
|
UTM(incrementer$, "111")
|
|
UTM(threeStateBB$, " ")
|
|
UTM(fiveStateBB$, " ", countOnly)
|