a turing machine simulator in the io language

turing.io

// Simple representation of a turing machine

Machine := Object clone

Machine tape := list()
Machine rule := Map clone
Machine pos := 0
Machine state := nil

Machine moveLeft := method (
    pos = pos - 1
    if (tape at(pos) == nil, tape prepend("0"); pos = 0)
)

Machine moveRight := method (
    pos = pos + 1
    if (tape at(pos) == nil, tape append("0"))
)

Machine insertRule := method (
    stateName, currentValue, nextState, action,
    rule atPut(stateName .. currentValue, list(nextState, action))
)

Machine displayTape := method (
    "-" print 
    for(a, 0, tape size - 1, 
        "+---" print
    )
    "+-" println
    " " print 
    for(a, 0, tape size - 1, 
        "| " print
        tape at(a) print
        " " print
    )
    "| " println
    "-" print 
    for(a, 0, tape size - 1, 
        "+---" print
    )
    "+-" println
    "   " print
    for(a, 0, pos - 1, 
        "    " print
    )
    "^" println
)

Machine step := method (
	if (rule at(state .. tape at(pos)) == nil, "halt" println; return false)
    newState := rule at(state .. tape at(pos)) at(0)
    action := rule at(state .. tape at(pos)) at(1)    
    state = newState
    if (action == "L") then (moveLeft; "moving left" println) elseif (action == "R") then (moveRight; "moving right" println) else (tape atPut(pos, action); "changing bit" println)
	return true
)

Machine execute := method (
	"starting program" println
	displayTape
	while(step == true,
		displayTape
	)
	"finished." println
)

// TESTING

adder := Machine clone
# 
adder insertRule("C1","0","1","C2")
adder insertRule("C1","1","R","C1")
adder insertRule("C2","0","R","C3")
adder insertRule("C2","1","L","C2")
adder insertRule("C3","0","R","C4")
adder insertRule("C3","1","0","C3")
adder insertRule("C4","0","R","C4")
# 
adder tape = list ("1", "1", "1", "1", "1", "0", "1", "1", "1", "0")
adder state = "C1"
adder execute
# 
# multi := Machine clone
# 
# multi insertRule("C1","1","L","C2")
# multi insertRule("C2","0","L","C3")
# multi insertRule("C2","1","L","C3")
# multi insertRule("C3","0","1","C3")
# multi insertRule("C3","1","L","C4")
# multi insertRule("C4","0","1","C4")
# multi insertRule("C4","1","R","C5")
# multi insertRule("C5","0","R","C6")
# multi insertRule("C5","1","R","C5")
# multi insertRule("C6","0","L","C7")
# multi insertRule("C6","1","R","C6")
# multi insertRule("C7","0","L","C8")
# multi insertRule("C7","1","0","C7")
# multi insertRule("C8","0","L","C11")
# multi insertRule("C8","1","L","C9")
# multi insertRule("C9","0","L","C10")
# multi insertRule("C9","1","L","C9")
# multi insertRule("C10","0","R","C2")
# multi insertRule("C10","1","L","C10")
# multi insertRule("C11","0","R","C12")
# multi insertRule("C11","1","L","C11")

#doubi := Machine clone

#doubi insertRule("C1", "1", "0", "C2") // delete the element to be doubled
#doubi insertRule("C2", "1", "L", "C2") // move left til zero
#doubi insertRule("C2", "0", "L", "C3") // move left til zero
// hit zero now move left til zero again
#doubi insertRule("C3", "1", "L", "C3") // move left til zero
#doubi insertRule("C3", "0", "1", "C4") // add first element

#doubi insertRule("C4", "1", "L", "C5") // move left
#doubi insertRule("C5", "0", "1", "C6") // add second element

#doubi insertRule("C6", "1", "R", "C6") // move to the zero
#doubi insertRule("C6", "0", "R", "C7") // move past the zero

#doubi insertRule("C7", "1", "R", "C7") // move to the last one
#doubi insertRule("C7", "0", "L", "C1") // go back

#doubi tape = list ("1", "1")
#doubi state = "C1"
#doubi execute