[SUMMARY] The Turing Machine (#162)

Discussion in 'Ruby' started by Matthew Moss, May 15, 2008.

  1. Matthew Moss

    Matthew Moss Guest

    While waiting for 48 hours to pass, several examples of Turing Machine
    code were sent in, including one example of over 1,500 lines,
    generated by code. Most others were simpler, handcrafted rulesets and
    tapes, dealing primarily with the limited input set of binary numbers.
    This kept code size smaller and easier to understand.

    A thought occurred to me that we might make an Extended Turing
    Machine, so we would no longer have to eliminate very repetitive state
    information. To take a small portion of one example:

    ...
    mark_start v mark_start v L
    mark_start w mark_start w L
    mark_start x mark_start x L
    mark_start y mark_start y L
    mark_start z mark_start z L
    mark_start _ mark_end S R
    mark_end a mark_end a R
    mark_end b mark_end b R
    mark_end c mark_end c R
    mark_end d mark_end d R
    ...

    Using a regular expression for the second argument with an implicit
    grouping, we could write our Turing Machines more easily.

    ...
    mark_start [a-z] mark_start $1 L
    mark_start _ mark_end S R
    mark_end [a-z] mark_end $1 R
    ...

    I don't doubt that there are other efficiencies we could impose on the
    simple Turing Machine language, to create a better language, a better
    Turing Machine. Yet, I think the point here is simply to explore the
    Turing Machine for what it is, rather than turn it into a higher level
    language. If we want that, we might as well stick with Ruby. (Still, a
    generator to help us write lengthy Turing Machine programs, such as
    was used for the 1500 line example, would be interesting.)

    I'm going to look at Alpha Chen's solution this week; it's short and
    simple, yet managed to surprise me a little. We start with the last
    line: the "main" of the solution.

    Turing.new(ARGV.shift, ARGV.shift).run if __FILE__ == $0

    Chen creates a new Turing Machine, passing in the first two command
    line arguments, but only if `__FILE__` (a constant containing the
    filename) is equal to `$0`. This is a typical check made to see if we
    are loading this module in an attempt to execute it, rather than
    loading it from another module via the `require` mechanism.

    Now to initializing the Turing class.

    def initialize(file, tape=nil)
    @tape = Hash.new('_')
    @head = 0

    # initialize tape
    tape.split(//).each_with_index {|c,i| @tape = c } if tape

    # read program instructions
    @program = Hash.new
    File.open(file).each_line do |line|
    line.gsub!(/#.*/, '') # remove comments
    next if line =~ /^\s*$/ # skip blank lines

    line = line.split(/\s+/)
    @state = line[0] if @state.nil?
    @program[line[0..1]] = line[2..4]
    end
    end

    The initialization of `@tape` as a Hash I missed the first time
    around. And it may seem strange to use a Hash to represent a tape,
    since Array would seem the proper fit. Still, the use of Hash here is
    clever to simplify other code later. It might not be a general purpose
    trick; still, we're implementing a Turing Machine here, which is
    hardly a critical application.

    Initializing `@tape` is slightly more complex because of this. The
    provided tape, if not nil, is broken into an array of characters by
    use of `split(//)`, but this must then be iterated over and each
    character inserted into the hash.

    Reading the program rules is pretty simple. As each line is read in,
    comments are first removed, and then blank lines are skipped via:

    next if line =~ /^\s*$/

    This regular expression matches the beginning of the line with `^`,
    then end of the line with `$`, and any amount of whitespace with
    `\s*`. If a blank line is found, `next` starts the next iteration of
    the loop.

    After the line is split into words, the program is stored in the
    `@program` hash with this:

    @program[line[0..1]] = line[2..4]

    Chen's program hash is keyed by two elements: the current machine
    state and the symbol under the machine head. These two items form a
    more complete state of the machine and keying the hash by this
    combined state makes for simple code later. To the hash, for that key,
    is inserted the rest of the rule.

    Running the machine in Chen's code is done as follows:

    def run
    while next_state = @program[[@state, @tape[@head]]]
    @state, @tape[@head], dir = next_state
    @head += (dir == 'R') ? 1 : -1
    end

    puts @tape.sort.map {|_,v| v}.join.gsub(/^_*|_*$/, '')
    end

    As mentioned above, looking up the next state requires keying into the
    program with two pieces of information: the current state and the
    symbol under the tape's head. If no entry can be found in the program,
    `next_state` will be nil and the loop will end.

    Otherwise, `next_state` is broken down into its three parts and
    assigned to the appropriate portions of the Turing Machine. The
    direction is used to update `@head`, either forward or backward one
    cell. This is where the use of `@tape` as a Hash, rather than an
    Array, simplifies the code. Chen no longer needs to check Array
    boundaries, to see if the tape needs to be extended to either the left
    or the right. Introducing a new "index" to `@tape` simply allocates
    another Hash entry.

    After the loop exits, the contents of the tape need to be output.
    Because `@tape` is a hash, there is a temptation to call `Hash#values`
    to get the content, but such is to be avoided, as I don't believe Ruby
    guarantees the order of the values. To get the values out in order
    along the tape, Chen uses `Hash#sort` with no block, which will sort
    key-value pairs Since the keys are first in each of those pairs, and
    the keys are the indices of the tape, the values will be sorted
    correctly.

    `map` is used to remove the keys and keep only the values, and `join`
    binds them back together into a single string. The final bit is a
    substitution attempting to strip off any external blanks, so only the
    "useful" content of the tape is displayed. Chen's regular expression
    (slightly corrected in the code shown above), removes all blanks
    immediately after the start of the line _or_ immediately preceding the
    end of the line.



    Tomorrow, we'll do some simple spam prevention...

    --
    Matthew Moss <>
     
    Matthew Moss, May 15, 2008
    #1
    1. Advertising

  2. Matthew Moss

    Alpha Chen Guest

    Re: The Turing Machine (#162)

    Thanks for the writeup!

    But a small nitpick... =)

    On May 15, 11:26 am, Matthew Moss <> wrote:
    >       puts @tape.sort.map {|_,v| v}.join.gsub(/^_*|_*$/, '')
    >
    > "useful" content of the tape is displayed. Chen's regular expression
    > (slightly corrected in the code shown above), removes all blanks
    > immediately after the start of the line _or_ immediately preceding the
    > end of the line.


    Shouldn't the regex return "a" instead of "a_b" for "_a_b_"?
     
    Alpha Chen, May 15, 2008
    #2
    1. Advertising

  3. Matthew Moss

    Matthew Moss Guest

    Re: The Turing Machine (#162)

    > Shouldn't the regex return "a" instead of "a_b" for "_a_b_"?

    No... the intent was that blanks be removed from the ends, but
    everything else retained.
     
    Matthew Moss, May 16, 2008
    #3
  4. Matthew Moss

    Alpha Chen Guest

    Re: The Turing Machine (#162)

    On May 15, 4:08 pm, Matthew Moss <> wrote:
    > > Shouldn't the regex return "a" instead of "a_b" for "_a_b_"?

    >
    > No... the intent was that blanks be removed from the ends, but
    > everything else retained.


    Oops, my mistake! Goes to show how well I can read the spec...
     
    Alpha Chen, May 16, 2008
    #4
  5. Matthew Moss

    Robert Dober Guest

    Re: The Turing Machine (#162)

    Great Quiz, I was offline but solved it anyway!
    Cheers
    Robert


    --
    http://ruby-smalltalk.blogspot.com/

    ---
    Whereof one cannot speak, thereof one must be silent.
    Ludwig Wittgenstein
     
    Robert Dober, May 16, 2008
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alex Vinokur
    Replies:
    0
    Views:
    750
    Alex Vinokur
    Nov 12, 2003
  2. Alex Vinokur
    Replies:
    0
    Views:
    700
    Alex Vinokur
    Dec 19, 2003
  3. Kvele

    Turing machine

    Kvele, Jan 7, 2005, in forum: C Programming
    Replies:
    3
    Views:
    1,271
    Jack Klein
    Jan 7, 2005
  4. roxorsoxor2345

    Programming a Turing Machine

    roxorsoxor2345, Dec 15, 2006, in forum: C++
    Replies:
    1
    Views:
    512
    frame
    Dec 15, 2006
  5. Matthew Moss

    [QUIZ] The Turing Machine (#162)

    Matthew Moss, May 9, 2008, in forum: Ruby
    Replies:
    26
    Views:
    545
    Matthew Moss
    May 13, 2008
Loading...

Share This Page