Universal Turing machine: Difference between revisions

Line 35:

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

def stay

# nop

end

def get_tape

return @tape

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}}==

===The universal machine===

Source for this example was lightly adapted from [https://bitbucket.org/ttmrichter/turing https://bitbucket.org/ttmrichter/turing]. Of particular interest in this implementation is that because of the type parameterisation of the <code>config</code> type, the machine being simulated cannot be compiled if there is any mistake in the states, symbols and actions. Also, because of Mercury's determinism detection and enforcement, it's impossible to pass in a non-deterministic set of rules. At most one answer can come back from the rules interface.

<lang mercury>:- module turing.

Line 201:

Line 97:

action(right, Blank, (Left-[])) = ([Blank|Left]-[]).

action(right, _, (Left-[Right|Rights])) = ([Right|Left]-Rights).</lang>

===The incrementer machine===

This machine has been stripped of the Mercury ceremony around modules, imports, etc.

<lang mercury>:- type incrementer_states ---> a ; halt.

:- type incrementer_symbols ---> b ; '1'.

Line 223:

Line 116:

TapeOut = turing(incrementer_config, incrementer, [1, 1, 1]).</lang>

This will, on execution, fill TapeOut with [1, 1, 1, 1].

===The busy beaver machine===

This machine has been stripped of the Mercury ceremony around modules, imports, etc.

<lang mercury>:- type busy_beaver_states ---> a ; b ; c ; halt.

:- type busy_beaver_symbols ---> '0' ; '1'.

Line 251:

Line 140:

TapeOut = turing(busy_beaver_config, busy_beaver, []).</lang>

This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].

=={{header|Prolog}}==

===The universal machine===

Source for this example was lightly adapted from [https://bitbucket.org/ttmrichter/turing https://bitbucket.org/ttmrichter/turing]. This machine, because of Prolog's dynamic nature, has to check its configuration and the rules' compliance to the same at run-time. This is the role of all but the first of the <code>memberchk/2</code> predicates. In addition, calling the user-supplied rules has to be wrapped in a <code>once/1</code> wrapper because there is no way to guarantee in advance that the rules provided are deterministic. (An alternative to doing this is to simply allow <code>perform/5</code> to be non-deterministic or to check for multiple results and report an error on such.)

<lang prolog>turing(Config, Rules, TapeIn, TapeOut) :-

call(Config, IS, _, _, _, _),

Line 291:

Line 176:

right(L, [], [B|L], [], B).

right(L, [S|Rs], [S|L], Rs, _).</lang>

===The incrementer machine===

<lang prolog>incrementer_config(IS, FS, RS, B, S) :-

IS = q0, % initial state

Line 304:

Line 187:

turing(incrementer_config, incrementer, [1, 1, 1], TapeOut).</lang>

This will, on execution, fill TapeOut with [1, 1, 1, 1].

===The busy beaver machine===

<lang prolog>busy_beaver_config(IS, FS, RS, B, S) :-

IS = 'A', % initial state

Line 323:

Line 203:

turing(busy_beaver_config, busy_beaver, [], TapeOut).</lang>

This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].

=={{header|Ruby}}==

This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].

===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

def stay

# nop

end

def get_tape

return @tape

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>