[QUIZ] The Turing Machine (#162)

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

  1. Matthew Moss

    Matthew Moss Guest

    -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

    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
     
    Matthew Moss, May 9, 2008
    #1
    1. Advertising

  2. Matthew Moss

    Matthew Moss Guest

    Re: The Turing Machine (#162)

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



    Forgot to put in the revised URL for the less-temporary website:

    <http://www.splatbang.com/rubyquiz>
     
    Matthew Moss, May 9, 2008
    #2
    1. Advertising

  3. Matthew Moss

    Chris Shea Guest

    Re: The Turing Machine (#162)

    On May 9, 9:48 am, 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


    I created another program for our Turning machines that reverses a
    string of zeros and ones.

    $ cat reverse.tm
    # Reverses a string of 0s and 1s
    mark_start 0 mark_start 0 L
    mark_start 1 mark_start 1 L
    mark_start _ mark_end S R

    mark_end 0 mark_end 0 R
    mark_end 1 mark_end 1 R
    mark_end _ rewind E L

    rewind 0 rewind 0 L
    rewind 1 rewind 1 L
    rewind S read_first S R

    read_first 0 append_0 _ L
    read_first 1 append_1 _ L
    read_first _ read_first _ R
    read_first E erase_marks _ L

    erase_marks _ erase_marks _ L
    erase_marks S done _ L

    append_0 S write_0 S L
    append_0 0 append_0 0 L
    append_0 1 append_0 1 L
    append_0 _ append_0 _ L

    append_1 S write_1 S L
    append_1 0 append_1 0 L
    append_1 1 append_1 1 L
    append_1 _ append_1 _ L

    write_0 0 write_0 0 L
    write_0 1 write_0 1 L
    write_0 _ find_start 0 R

    write_1 0 write_1 0 L
    write_1 1 write_1 1 L
    write_1 _ find_start 1 R

    find_start 0 find_start 0 R
    find_start 1 find_start 1 R
    find_start S read_first S R

    $ ruby tm.rb reverse.tm 1011
    1101


    The names of the states could probably use some improvement, and maybe
    there's a more efficient implementation, but there it is. I hope
    others share some.

    Chris
     
    Chris Shea, May 9, 2008
    #3
  4. Matthew Moss

    Adam Shelly Guest

    Re: The Turing Machine (#162)

    On 5/9/08, Chris Shea <> wrote:
    > I created another program for our Turning machines that reverses a
    > string of zeros and ones.

    ...
    > I hope others share some.
    >

    Here's a simple one.

    $ cat add1.rb
    #adds 1 to a binary number
    seekLSB 1 seekLSB 1 R
    seekLSB 0 seekLSB 0 R
    seekLSB _ add1 _ L
    add1 1 add1 0 L
    add1 0 done 1 L
    add1 _ done 1 L

    $ruby turing.rb add1.rb 0
    1
    $ruby turing.rb add1.rb 1011
    1100

    -Adam
     
    Adam Shelly, May 9, 2008
    #4
  5. Does it mean the tape head move action can only be [RL] ? Is there an
    instruction for not moving the head?

    On Fri, May 9, 2008 at 11:48 PM, 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
    >
    >
    >




    --
    pluskid
     
    Chiyuan Zhang, May 10, 2008
    #5
  6. Matthew Moss

    James Gray Guest

    On May 9, 2008, at 11:23 PM, Chiyuan Zhang wrote:

    > Does it mean the tape head move action can only be [RL] ? Is there an
    > instruction for not moving the head?


    Correct, the tape moves with each instruction.

    James Edward Gray II
     
    James Gray, May 10, 2008
    #6
  7. Re: The Turing Machine (#162)

    Chris Shea wrote:
    > ... I hope others share some.


    Below is a (very ugly) machine to convert binary to octal,
    since it seems binary is the popular test representation.

    $ ruby quiz-162 to_oct.tm
    0

    $ ruby quiz-162 to_oct.tm 0
    0

    $ ruby quiz-162 to_oct.tm 101
    5

    $ ruby quiz-162 to_oct.tm 000001010011100101110111
    1234567

    An annotated example:
    $ ruby quiz-162 to_oct.tm 0011101
    # Span to the end of the binary digits; mark the end.
    span_end 0 -> span_endB 0 R : >0< 0 1 1 1 0 1
    span_endB 0 -> span_endB 0 R : 0 >0< 1 1 1 0 1
    span_endB 1 -> span_endB 1 R : 0 0 >1< 1 1 0 1
    span_endB 1 -> span_endB 1 R : 0 0 1 >1< 1 0 1
    span_endB 1 -> span_endB 1 R : 0 0 1 1 >1< 0 1
    span_endB 0 -> span_endB 0 R : 0 0 1 1 1 >0< 1
    span_endB 1 -> span_endB 1 R : 0 0 1 1 1 0 >1<
    span_endB _ -> cvt_xxx X L : 0 0 1 1 1 0 1 >_<
    # Convert each set of three binary digits to an octal digit.
    cvt_xxx 1 -> cvt_xx1 _ L : 0 0 1 1 1 0 >1< X
    cvt_xx1 0 -> cvt_x01 _ L : 0 0 1 1 1 >0< _ X
    cvt_x01 1 -> cvt_xxx 5 L : 0 0 1 1 >1< _ _ X
    cvt_xxx 1 -> cvt_xx1 _ L : 0 0 1 >1< 5 _ _ X
    cvt_xx1 1 -> cvt_x11 _ L : 0 0 >1< _ 5 _ _ X
    cvt_x11 0 -> cvt_xxx 3 L : 0 >0< _ _ 5 _ _ X
    cvt_xxx 0 -> cvt_xx0 _ L : >0< 3 _ _ 5 _ _ X
    cvt_xx0 _ -> squeeze 0 L : >_< _ 3 _ _ 5 _ _ X
    # Squeeze intervening spaces.
    squeeze _ -> squeezeA _ R : >_< 0 _ 3 _ _ 5 _ _ X
    squeezeA 0 -> squeezeA _ R : _ >0< _ 3 _ _ 5 _ _ X
    squeezeA _ -> squeezeA _ R : _ _ >_< 3 _ _ 5 _ _ X
    squeezeA 3 -> squeezeB 3 R : _ _ _ >3< _ _ 5 _ _ X
    squeezeB _ -> squeezeC X R : _ _ _ 3 >_< _ 5 _ _ X
    squeezeC _ -> squeezeC _ R : _ _ _ 3 X >_< 5 _ _ X
    squeezeC 5 -> squeeze5 _ L : _ _ _ 3 X _ >5< _ _ X
    squeeze5 _ -> squeeze5 _ L : _ _ _ 3 X >_< _ _ _ X
    squeeze5 X -> squeezeD 5 R : _ _ _ 3 >X< _ _ _ _ X
    squeezeD _ -> squeezeC X R : _ _ _ 3 5 >_< _ _ _ X
    squeezeC _ -> squeezeC _ R : _ _ _ 3 5 X >_< _ _ X
    squeezeC _ -> squeezeC _ R : _ _ _ 3 5 X _ >_< _ X
    squeezeC _ -> squeezeC _ R : _ _ _ 3 5 X _ _ >_< X
    squeezeC X -> squeezeX _ L : _ _ _ 3 5 X _ _ _ >X<
    squeezeX _ -> squeezeX _ L : _ _ _ 3 5 X _ _ >_< _
    squeezeX _ -> squeezeX _ L : _ _ _ 3 5 X _ >_< _ _
    squeezeX _ -> squeezeX _ L : _ _ _ 3 5 X >_< _ _ _
    squeezeX X -> __done__ _ L : _ _ _ 3 5 >X< _ _ _ _
    __done__ 5 -> --none-- : _ _ _ 3 >5< _ _ _ _ _
    ---> '35'

    $ cat to_oct.tm

    #
    # Convert binary to octal.
    #

    #
    # Span to the end of the binary digits; mark the end.
    #
    span_end 0 span_endB 0 R
    span_end 1 span_endB 1 R
    span_end _ __done__ 0 R
    span_endB 0 span_endB 0 R
    span_endB 1 span_endB 1 R
    span_endB _ cvt_xxx X L

    #
    # Convert each set of three binary digits to an octal digit.
    #
    cvt_xxx 0 cvt_xx0 _ L
    cvt_xxx 1 cvt_xx1 _ L
    cvt_xxx _ squeeze 0 L

    cvt_xx0 0 cvt_x00 _ L
    cvt_xx0 1 cvt_x10 _ L
    cvt_xx0 _ squeeze 0 L

    cvt_x00 0 cvt_xxx 0 L
    cvt_x00 1 cvt_xxx 4 L
    cvt_x00 _ squeeze 0 L

    cvt_x10 0 cvt_xxx 2 L
    cvt_x10 1 cvt_xxx 6 L
    cvt_x10 _ squeeze 2 L

    cvt_xx1 0 cvt_x01 _ L
    cvt_xx1 1 cvt_x11 _ L
    cvt_xx1 _ squeeze 1 L

    cvt_x01 0 cvt_xxx 1 L
    cvt_x01 1 cvt_xxx 5 L
    cvt_x01 _ squeeze 1 L

    cvt_x11 0 cvt_xxx 3 L
    cvt_x11 1 cvt_xxx 7 L
    cvt_x11 _ squeeze 3 L

    #
    # Squeeze intervening spaces.
    #
    squeeze _ squeeze _ R
    squeeze 0 squeeze _ R
    squeeze 1 squeezeB 1 R
    squeeze 2 squeezeB 2 R
    squeeze 3 squeezeB 3 R
    squeeze 4 squeezeB 4 R
    squeeze 5 squeezeB 5 R
    squeeze 6 squeezeB 6 R
    squeeze 7 squeezeB 7 R
    squeeze X __done__ 0 R
    squeezeB _ squeezeC X R
    squeezeC _ squeezeC _ R

    squeezeC 0 squeeze0 _ L
    squeeze0 _ squeeze0 _ L
    squeeze0 X squeezeD 0 R
    squeezeD _ squeezeC X R

    squeezeC 1 squeeze1 _ L
    squeeze1 _ squeeze1 _ L
    squeeze1 X squeezeD 1 R

    squeezeC 2 squeeze2 _ L
    squeeze2 _ squeeze2 _ L
    squeeze2 X squeezeD 2 R

    squeezeC 3 squeeze3 _ L
    squeeze3 _ squeeze3 _ L
    squeeze3 X squeezeD 3 R

    squeezeC 4 squeeze4 _ L
    squeeze4 _ squeeze4 _ L
    squeeze4 X squeezeD 4 R

    squeezeC 5 squeeze5 _ L
    squeeze5 _ squeeze5 _ L
    squeeze5 X squeezeD 5 R

    squeezeC 6 squeeze6 _ L
    squeeze6 _ squeeze6 _ L
    squeeze6 X squeezeD 6 R

    squeezeC 7 squeeze7 _ L
    squeeze7 _ squeeze7 _ L
    squeeze7 X squeezeD 7 R

    squeezeC X squeezeX _ L
    squeezeX _ squeezeX _ L
    squeezeX X __done__ _ L
     
    Glen F. Pankow, May 10, 2008
    #7
  8. Matthew Moss

    Juanger Guest

    In fact, both representations are equivalent(the one that has the option to
    stay in the same cell and the one that doesn't).
    In our case, you will have to use another state to emulate that behaviour.

    On Fri, May 9, 2008 at 11:42 PM, James Gray <>
    wrote:

    > On May 9, 2008, at 11:23 PM, Chiyuan Zhang wrote:
    >
    > Does it mean the tape head move action can only be [RL] ? Is there an
    >> instruction for not moving the head?
    >>

    >
    > Correct, the tape moves with each instruction.
    >
    > James Edward Gray II
    >
    >



    --=20
    Ash Mac durbatul=FBk, ash Mac gimbatul, ash Mac thrakatul=FBk agh burzum-is=
    hi
    krimpatul.
    Juanger.
     
    Juanger, May 10, 2008
    #8
  9. Matthew Moss

    Adam Shelly Guest

    Re: The Turing Machine (#162)

    On Fri, May 9, 2008 at 10:22 PM, Glen F. Pankow <> wrote:
    > Chris Shea wrote:
    >> ... I hope others share some.

    >
    > Below is a (very ugly) machine to convert binary to octal,
    > since it seems binary is the popular test representation.
    >

    That's an interesting solution. When I wrote my binary to hex
    converter I took a fairly different approach. I think binary is
    popular because it limits the number of state transitions required.
    Compare my seekLSB state to the exitHex state - both do the same
    thing, but the one that supports hex is 6 times bigger.
    -Adam

    --------------
    ## bin2hex.tm
    ## converts binary to hex
    ## by creating an accumulator (the store)
    ## to the left of the input, and moving one
    ## bit at a time from the input to the store

    #first find the MSB of the input
    seekMSB 1 seekMSB 1 L
    seekMSB 0 seekMSB 0 L
    seekMSB _ makeStore _ L

    #creates the storage for the hex value: tape:= 0_<input>
    makeStore _ moveRight 0 R

    #goes to lsb of input
    moveRight _ seekLSB _ R
    seekLSB 1 seekLSB 1 R
    seekLSB 0 seekLSB 0 R
    seekLSB _ dec _ L

    #decrement binary, starting from LSB
    #when we get to a 1 we are done
    #if we get to a _ we must have started with all 0s .
    dec 0 dec 1 L
    dec 1 findStore 0 L
    dec _ clearRight _ R #so just cleanup the original input

    #seeks back to the store
    findStore 0 findStore 0 L
    findStore 1 findStore 1 L
    findStore _ addToStore _ L

    #adds 1 to store
    addToStore _ exitHex 1 R
    addToStore 0 exitHex 1 R
    addToStore 1 exitHex 2 R
    addToStore 2 exitHex 3 R
    addToStore 3 exitHex 4 R
    addToStore 4 exitHex 5 R
    addToStore 5 exitHex 6 R
    addToStore 6 exitHex 7 R
    addToStore 7 exitHex 8 R
    addToStore 8 exitHex 9 R
    addToStore 9 exitHex A R
    addToStore A exitHex B R
    addToStore B exitHex C R
    addToStore C exitHex D R
    addToStore D exitHex E R
    addToStore E exitHex F R
    addToStore F addToStore 0 L #carry

    #move head back into the input
    exitHex 0 exitHex 0 R
    exitHex 1 exitHex 1 R
    exitHex 2 exitHex 2 R
    exitHex 3 exitHex 3 R
    exitHex 4 exitHex 4 R
    exitHex 5 exitHex 5 R
    exitHex 6 exitHex 6 R
    exitHex 7 exitHex 7 R
    exitHex 8 exitHex 8 R
    exitHex 9 exitHex 9 R
    exitHex A exitHex A R
    exitHex B exitHex B R
    exitHex C exitHex C R
    exitHex D exitHex D R
    exitHex E exitHex E R
    exitHex F exitHex F R
    exitHex _ seekLSB _ R

    #erase a binary string to the right
    clearRight 0 clearRight _ R
    clearRight 1 clearRight _ R
    clearRight _ done _ L #done cleanup, ready to print
     
    Adam Shelly, May 10, 2008
    #9
  10. Matthew Moss

    Matthew Moss Guest

    Re: The Turing Machine (#162)

    Just so you guys know, I have no intentions of starting Turning
    Machine Quiz. I have enough work to do as it is writing summaries for
    Ruby Quiz, and I *really* don't want to read a bunch of turing machine
    code.


    :) Just kidding...


    (No I'm not. ;)
     
    Matthew Moss, May 11, 2008
    #10
  11. Matthew Moss

    Chris Shea Guest

    Re: The Turing Machine (#162)

    On May 10, 10:20 pm, Matthew Moss <> wrote:
    > Just so you guys know, I have no intentions of starting Turning
    > Machine Quiz. I have enough work to do as it is writing summaries for
    > Ruby Quiz, and I *really* don't want to read a bunch of turing machine
    > code.
    >
    > :) Just kidding...
    >
    > (No I'm not. ;)


    Too bad. I've started on a DSL for creating Turing machine code. I
    just generated a 1,568 line program to reverse a lowercase word.

    $ ./tm rev.tm ruby
    ybur
    $ ./tm rev.tm turing
    gnirut
    $ ./tm rev.tm racecar
    racecar
    $ time ./tm rev.tm abcdefghijklmnopqrstuvwxyz
    zyxwvutsrqponmlkjihgfedcba
    0.84s user 0.01s system 99% cpu 0.857 total

    http://pastie.textmate.org/195072

    Chris
     
    Chris Shea, May 11, 2008
    #11
  12. Matthew Moss

    ThoML Guest

    ThoML, May 11, 2008
    #12
  13. Matthew Moss

    Chris Shea Guest

    Re: The Turing Machine (#162)

    On May 11, 2:14 am, ThoML <> wrote:
    > > I've started on a DSL for creating Turing machine code.

    >
    > Yummy. Please share.


    Unless it's going to be a follow-up quiz. I think it'd make a great
    series of follow-up quizzes. First we abstract the Turing machine a
    little, then a little more, and a little more, and up until we write a
    Ruby implementation.

    Chris
     
    Chris Shea, May 11, 2008
    #13
  14. Matthew Moss

    Chris Carter Guest

    Re: The Turing Machine (#162)

    On Sat, May 10, 2008 at 11:20 PM, Matthew Moss <> wrote:
    > Just so you guys know, I have no intentions of starting Turning
    > Machine Quiz. I have enough work to do as it is writing summaries for
    > Ruby Quiz, and I *really* don't want to read a bunch of turing machine
    > code.


    I am surprised nobody has shared their Hello World!

    saurasaurus:~ cdcarter$ cat hello.tm
    # Hello World!
    curr_state _ h h R
    h _ e e R
    e _ l l R
    l _ l2 l R
    l2 _ o o R
    o _ w w R
    w _ o2 o R
    o2 _ r r R
    r _ l3 l R
    l3 _ d d R
    d _ ex ! R



    --
    Chris Carter
    concentrationstudios.com
    brynmawrcs.com
     
    Chris Carter, May 11, 2008
    #14
  15. Matthew Moss

    Chris Shea Guest

    Re: The Turing Machine (#162)

    On May 9, 9:48 am, 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


    It looks like it's been 48 hours, so here's what I whipped up:
    http://pastie.textmate.org/195153

    I hope it's pretty straightforward.

    Chris
     
    Chris Shea, May 11, 2008
    #15
  16. Matthew Moss

    ThoML Guest

    Re: The Turing Machine (#162)

    > It looks like it's been 48 hours

    Already. Ok, so here is mine.


    #!/usr/bin/env ruby

    def tm(rules, q, input)
    directions = {'L' => -1, 'R' => 1}
    tape = input ? input.split(//) : []
    p = 0
    loop do
    q, c, d = rules[[q, tape[p] || '_']]
    return tape.join unless q
    tape[p] = c == '_' ? nil : c
    p += directions[d] || raise('Unknown direction: %s' % d)
    if p == -1
    tape.unshift(nil)
    p = 0
    end
    end
    end

    def read_rules(file)
    rules = {}
    q = nil
    File.readlines(file).each do |l|
    a = l.scan(/#|\S+/)
    next if a[0] == '#' or a.empty?
    q ||= a[0]
    rules[a[0,2]] = a[2,5]
    end
    return [rules, q]
    end

    if __FILE__ == $0
    file, input = ARGV
    puts tm(*read_rules(file), input)
    end
     
    ThoML, May 11, 2008
    #16
  17. Matthew Moss

    Chris Carter Guest

    Chris Carter, May 11, 2008
    #17
  18. Re: The Turing Machine (#162)

    This is my solution, I tried to keep it clean (also if I found quite
    hard implement the Tape model)

    Hope you like it :D
    Solution: http://pastie.textmate.org/195173

    On Sun, May 11, 2008 at 5:31 PM, Chris Carter <> wrote:
    >> It looks like it's been 48 hours, so here's what I whipped up:
    >> http://pastie.textmate.org/195153
    >>
    >> I hope it's pretty straightforward.
    >>
    >> Chris

    >
    > Here's mine:
    > http://pastie.textmate.org/195165
    >
    > It is pretty simple, and short.
    >
    > --
    > Chris Carter
    > concentrationstudios.com
    > brynmawrcs.com
    >
    >




    --
    Go outside! The graphics are amazing!
     
    Sandro Paganotti, May 11, 2008
    #18
  19. Andrew Thompson, May 11, 2008
    #19
  20. On Fri, May 9, 2008 at 5:48 PM, Matthew Moss <> wrote:
    > ## 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.


    Hi,

    This is what I did: the TuringMachine is made of a TuringTape, a
    String for the current state and a hash of instructions. The
    TuringTape represents the infinite tape, and it's an array of chars
    and a pointer to the current position, with methods for reading,
    writing and moving the head. The instructions have a string and a char
    as the key for the hash, and the value of the hash is a new state, a
    char to write and a head move. The rest of the program is just reading
    a file and the initial tape values and running the program, which
    involves finding an instruction for the current state and char, and
    executing the instruction (changing the state, writing the char and
    moving the head):

    InstructionCondition = Struct.new :state, :char
    InstructionAction = Struct.new :next_state, :char, :head_move

    class TuringTape
    def initialize contents=nil
    @contents = (contents || "_").split ""
    @head = 0
    end

    def move_head dir
    if dir == :R
    @head += 1
    unless @contents[@head]
    @contents << "_"
    end
    else
    if @head == 0
    @contents.unshift "_"
    else
    @head -= 1
    end
    end
    self
    end

    def read
    @contents[@head]
    end

    def write char
    @contents[@head] = char
    end

    def contents
    @contents.join.tr("_", " ").strip
    end
    end

    class TuringMachine
    def initialize program, initial_tape_contents
    @tape = TuringTape.new initial_tape_contents
    @program = {}
    @current_state = nil
    program.each do |line|
    # skip comment lines
    next if line =~ /\A\s*\#/
    current_state, char, next_state, char_to_write, head_move =
    line.split(" ")
    # skip blank lines
    next unless current_state
    # The starting state will be the first one found in the program
    unless @current_state
    @current_state = current_state
    end
    @program[InstructionCondition.new(current_state, char)] =
    InstructionAction.new(next_state, char_to_write, head_move.to_sym)
    end
    end

    def run
    while instruction =
    @program[InstructionCondition.new(@current_state, @tape.read)]
    @current_state = instruction.next_state
    @tape.write instruction.char
    @tape.move_head instruction.head_move
    end
    @tape.contents
    end
    end

    program = File.read(ARGV[0])
    tape = ARGV[1]
    puts TuringMachine.new(program,tape).run

    Thanks for the quiz,

    Jesus.
     
    Jesús Gabriel y Galán, May 11, 2008
    #20
    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:
    735
    Alex Vinokur
    Nov 12, 2003
  2. Alex Vinokur
    Replies:
    0
    Views:
    676
    Alex Vinokur
    Dec 19, 2003
  3. Kvele

    Turing machine

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

    Programming a Turing Machine

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

    [SUMMARY] The Turing Machine (#162)

    Matthew Moss, May 15, 2008, in forum: Ruby
    Replies:
    4
    Views:
    203
    Robert Dober
    May 16, 2008
Loading...

Share This Page