 |
| Prev-20 | Home | Next-20 |
| Prev-20 | Home | Next-20 |
| Prev-Msg | Prev-Thread | Ruby-talk | May-2008 | Next-Thread | Next-Msg |
| Subject: | Re: [QUIZ] The Turing Machine (#162) |
| Group: | Ruby-talk |
| From: | Juanger |
| Date: | 11 May 2008 |
I attached my solution.
On Fri, May 9, 2008 at 10:48 AM, Matthew Moss <matthew.moss>
wrote:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> The three rules of Ruby Quiz 2:
>
> 1. Please do not post any solutions or spoiler discussion for this
> quiz until 48 hours have passed from the time on this message.
>
> 2. Support Ruby Quiz 2 by submitting ideas as often as you can! (A
> permanent, new website is in the works for Ruby Quiz 2. Until then,
> please visit the temporary website at
>
> <http://matthew.moss.googlepages.com/home>.
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem
> helps everyone on Ruby Talk follow the discussion. Please reply to
> the original quiz message, if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> ## The Turing Machine
>
> _Quiz description by James Edward Gray II_
>
> The Turing Machine is a simple computing architecture dating all the
> way back to the 1930s. While extremely primitive compared to any
> modern machine, there has been a lot of research showing that a Turing
> Machine is capable of just about anything the fancier machines can do
> (although much less efficiently, of course).
>
> This week's task is to build a Turing Machine, so we can play around
> with the architecture.
>
> A Turing Machine has but three simple parts:
>
> * A single state register.
> * An infinite tape of memory cells that can hold one character
> each, with a
> read/write head that points to one of these cells at any given
> time. The
> tape is filled with an infinite run of blank characters in
> either
> direction.
> * A finite set of program instructions. The program is just a big
> table of
> state transitions. The Turing Machine will look up an
> instruction based
> the current value of the state register and the current
> character under
> head of the tape. That instruction will provide a state for
> the
> register, a character to place in the current memory cell, and
> an order to
> move the head to the left or the right.
>
> To keep our Turning Machine simple, let's say that our state register
> can contain words matching the regular expression `/\w+/` and the tape
> only contains characters that match the expression `/\w/`. We will
> call our blank tape cell character the underscore.
>
> Program lines will be of the form:
>
> CurrentState _ NewState C R
>
> The above translates to: if the current state is CurrentState and the
> character under the tape head is our blank character, set the state to
> NewState, replace the blank character with a C, and move the tape head
> to the right one position. All five elements will be present in each
> line and separated by one or more whitespace characters. Allow for
> trailing comments (using #) on a line, comment only lines, and blank
> lines in the program by ignoring all three.
>
> The initial state of your Turing machine should be set to the
> CurrentState mentioned on the first line of the program. Optionally,
> the initial contents of the tape can be provided when the program is
> load, but it will default to an all blank tape. The program runs
> until it fails to find an instruction for the CurrentState and the
> character currently under the tape head, at which point it prints the
> current contents of the tape head from the first non-blank character
> to the last non-blank character and exits.
>
> Here's a sample run of a simple program through my Turing Machine so
> you can see how this plays out:
>
> $ cat palindrome.tm
> # Report whether a string of 0 and 1 (ie. a binary
> # number) is a palindrome.
> look_first 0 go_end_0 _ R
> look_first 1 go_end_1 _ R
> look_first _ write_es Y R
> go_end_0 0 go_end_0 0 R
> go_end_0 1 go_end_0 1 R
> go_end_0 _ check_end_0 _ L
> go_end_1 0 go_end_1 0 R
> go_end_1 1 go_end_1 1 R
> go_end_1 _ check_end_1 _ L
> check_end_0 0 ok_rewind _ L
> check_end_0 1 fail_rewind _ L
> check_end_0 _ ok_rewind _ L
> check_end_1 0 fail_rewind _ L
> check_end_1 1 ok_rewind _ L
> check_end_1 _ ok_rewind _ L
> ok_rewind 0 ok_rewind 0 L
> ok_rewind 1 ok_rewind 1 L
> ok_rewind _ look_first _ R
> fail_rewind 0 fail_rewind _ L
> fail_rewind 1 fail_rewind _ L
> fail_rewind _ write_o N R
> write_es _ write_s e R
> write_o _ done o R
> write_s _ done s R
>
> $ ruby tm.rb palindrome.tm 011010110
> Yes
>
> $ ruby tm.rb palindrome.tm 01101
> No
>
>
>
--
Ash Mac durbatulűk, ash Mac gimbatul, ash Mac thrakatulűk agh burzum-ishi
krimpatul.
Juanger.
class TuringMachine
attr_accessor :tape
def initialize(instructions, input = "")
@move = {"R" => :right, "L" => :left} # Translator for R and L
@tape = Tape.new(input) # The infinite tape
@head = @tape.head # The reading-writing head
@delta = Hash.new # Our delta function
@state = nil # The current state
fill_delta(instructions)
run
end
private
# Fills the delta function hash
def fill_delta(instructions)
if File.file? instructions
open(instructions, "r") { |file|
i = 0
file.each { |line|
next if line =~ /^(#.*)?$/
parse_rule(line, i == 0)
i += 1
}
}
end
end
# Defines the keys/values for the hash
def parse_rule(rule_line, first = false)
rule = rule_line.split
@delta[[rule[0], rule[1]]] = [rule[2], rule[3], rule[4]]
@state = rule[0] if first # initial value for @state
end
# Go TuringMachine, Go!!
def run
step = @delta[[@state,@head.char]] # Calculates the next step
while step
@state = step[0]
@head.char = step[1]
@head = @head.send(@move[step[2]])
step = @delta[[@state,@head.char]]
end
@tape.display # Print the tape
end
end
class Tape
attr_accessor :head
def initialize(input)
if input.size > 0
i = 0
last = nil
actual = nil
input.scan(/./m) { |c| # Create the Cells and link them
actual = Cell.new(c)
if i == 0
@head = last = actual
else
last.right = actual
actual.left = last
last = actual
end
i += 1
}
else
@head = Cell.new("_")
end
end
# Print the non-blank contents of the tape
def display
until @head.left_boundary? # rewind to the begining
@head = @head.left
end
until @head.right_boundary? # print each char to the end
print @head.char unless @head.char == "_"
@head = @head.right
end
puts ""
end
end
class Cell
attr_accessor :char
attr_writer :right, :left
def initialize(char, left = nil, right = nil)
@char = char
@right = right
@left = left
end
# Get the cell at the right
# Creates a cell with a blank character as needed
def right
unless @right
@right = Cell.new("_", self, nil)
end
@right
end
# Get the cell at the left
# Creates a cell with a blank character as needed
def left
unless @left
@left = Cell.new("_", nil, self)
end
@left
end
# Is it the first defined cell in the tape??
def left_boundary?
unless @left
true
else
false
end
end
# Is it the last defined cell in the tape??
def right_boundary?
unless @right
true
else
false
end
end
end
case ARGV.size
when 0
puts "I need a program !!"
when 1
tm = TuringMachine.new(ARGV[0])
when 2
tm = TuringMachine.new(ARGV[0], ARGV[1])
end
| Prev-Msg | Prev-Thread | Ruby-talk | May-2008 | Next-Thread | Next-Msg |