63 lines
1.7 KiB
Ruby
63 lines
1.7 KiB
Ruby
class Turing
|
|
class Tape
|
|
def initialize(symbols, blank, starting_tape)
|
|
@symbols = symbols
|
|
@blank = blank
|
|
@tape = starting_tape
|
|
@index = 0
|
|
end
|
|
def read
|
|
retval = @tape[@index]
|
|
unless retval
|
|
retval = @tape[@index] = @blank
|
|
end
|
|
raise "invalid symbol '#{retval}' on tape" unless @tape.member?(retval)
|
|
return retval
|
|
end
|
|
def write(symbol)
|
|
@tape[@index] = symbol
|
|
end
|
|
def right
|
|
@index += 1
|
|
end
|
|
def left
|
|
if @index == 0
|
|
@tape.unshift @blank
|
|
else
|
|
@index -= 1
|
|
end
|
|
end
|
|
def stay
|
|
# nop
|
|
end
|
|
def get_tape
|
|
return @tape
|
|
end
|
|
end
|
|
|
|
def initialize(symbols, blank,
|
|
initial_state, halt_states, running_states,
|
|
rules, starting_tape = [])
|
|
@tape = Tape.new(symbols, blank, starting_tape)
|
|
@initial_state = initial_state
|
|
@halt_states = halt_states
|
|
@running_states = running_states
|
|
@rules = rules
|
|
@halted = false
|
|
end
|
|
def run
|
|
raise "machine already halted" if @halted
|
|
state = @initial_state
|
|
while (true)
|
|
break if @halt_states.member? state
|
|
raise "unknown state '#{state}'" unless @running_states.member? state
|
|
symbol = @tape.read
|
|
outsym, action, state = @rules[state][symbol]
|
|
@tape.write outsym
|
|
@tape.send action
|
|
end
|
|
@halted = true
|
|
return @tape.get_tape
|
|
end
|
|
end
|