Universal Turing machine: Difference between revisions
Content added Content deleted
No edit summary |
No edit summary |
||
Line 35: | Line 35: | ||
The input for this machine should be an empty tape. |
The input for this machine should be an empty tape. |
||
=={{header|Ruby}}== |
|||
===The universal machine=== |
|||
<lang 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</lang> |
|||
===The incrementer machine=== |
|||
<lang ruby>incrementer_rules = { |
|||
:q0 => { 1 => [1, :right, :q0], |
|||
:b => [1, :stay, :qf]} |
|||
} |
|||
t = Turing.new([:b, 1], # permitted symbols |
|||
:b, # blank symbol |
|||
:q0, # starting state |
|||
[:qf], # terminating states |
|||
[:q0], # running states |
|||
incrementer_rules, # operating rules |
|||
[1, 1, 1]) # starting tape |
|||
print t.run, "\n"</lang> |
|||
===The busy beaver machine=== |
|||
<lang ruby>busy_beaver_rules = { |
|||
:a => { 0 => [1, :right, :b], |
|||
1 => [1, :left, :c]}, |
|||
:b => { 0 => [1, :left, :a], |
|||
1 => [1, :right, :b]}, |
|||
:c => { 0 => [1, :left, :b], |
|||
1 => [1, :stay, :halt]} |
|||
} |
|||
t = Turing.new([0, 1], # permitted symbols |
|||
0, # blank symbol |
|||
:a, # starting state |
|||
[:halt], # terminating states |
|||
[:a, :b, :c], # running states |
|||
busy_beaver_rules, # operating rules |
|||
[]) # starting tape |
|||
print t.run, "\n"</lang> |
|||
=={{header|Mercury}}== |
=={{header|Mercury}}== |