Matthew Moss | 15 May 20:25
Picon

[SUMMARY] The Turing Machine (#162)

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
(Continue reading)

Alpha Chen | 16 May 00:00
Picon

Re: The Turing Machine (#162)

Thanks for the writeup!

But a small nitpick... =)

On May 15, 11:26 am, Matthew Moss <matthew.m...@gmail.com> 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_"?

Matthew Moss | 16 May 01:08
Picon

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.

Alpha Chen | 16 May 01:25
Picon

Re: The Turing Machine (#162)

On May 15, 4:08 pm, Matthew Moss <matthew.m...@gmail.com> 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...

Robert Dober | 16 May 21:15
Picon

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


Gmane