# The Turing Machine (#162)

**URL:** <https://www.ruby-forum.com/t/the-turing-machine-162/137734>\
**Category:** Ruby\
**Created:** [May 15, 2008, 8:27pm UTC](https://www.ruby-forum.com/t/the-turing-machine-162/137734 "2008-05-15T20:27:18Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [May 15, 2008, 8:27pm UTC](https://www.ruby-forum.com/t/the-turing-machine-162/137734/1 "2008-05-15T20:27:18Z")

</div>

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[i] = 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…

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [May 16, 2008, 12:00am UTC](https://www.ruby-forum.com/t/the-turing-machine-162/137734/2 "2008-05-16T00:00:43Z")

</div>

Thanks for the writeup!

But a small nitpick… =)

On May 15, 11:26 am, Matthew M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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_”?

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [May 16, 2008, 1:08am UTC](https://www.ruby-forum.com/t/the-turing-machine-162/137734/3 "2008-05-16T01:08:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [May 16, 2008, 1:25am UTC](https://www.ruby-forum.com/t/the-turing-machine-162/137734/4 "2008-05-16T01:25:47Z")

</div>

On May 15, 4:08 pm, Matthew M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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…

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [May 16, 2008, 9:16pm UTC](https://www.ruby-forum.com/t/the-turing-machine-162/137734/5 "2008-05-16T21:16:42Z")

</div>

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

–  
[http://ruby-smalltalk.blogspot.com/](http://ruby-smalltalk.blogspot.com/)

* * *

Whereof one cannot speak, thereof one must be silent.  
Ludwig Wittgenstein