# Re: The Turing Machine (#162)

**URL:** <https://www.ruby-forum.com/t/re-the-turing-machine-162/137549>\
**Category:** Ruby\
**Created:** [May 14, 2008, 3:59am UTC](https://www.ruby-forum.com/t/re-the-turing-machine-162/137549 "2008-05-14T03:59:40Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [May 14, 2008, 3:59am UTC](https://www.ruby-forum.com/t/re-the-turing-machine-162/137549/1 "2008-05-14T03:59:40Z")

</div>

I was a little late submitting this week, so, rather than fleshing this  
solution out, I just challenged myself to write a short but good  
program. I think I did a pretty good job, at 33 lines of non-golfed  
code.

Thanks to Andrew J. and his solution to RubyQuiz 69 for showing me  
the trick of using hashes for lazy evaluation.

state = nil  
instructions = File.open(ARGV[0]) do |f|  
f.readlines.map{|s|  
(s=s.match(/^[^#]+/)[0].strip).empty? ? nil :  
s}.compact.  
inject({}){|hsh,s|  
md=s.match(/(\w+)\s+(\w)\s+(\w+)\s+(\w)\s+([LR])/)  
state = state || md[1]  
hsh[[md[1],md[2]]]=[md[3],md[4],md[5]]  
hsh  
}  
end

tape = Hash.new do |cell,v|  
h = cell.dup  
h[:C] = ‘\_’  
h[v==‘L’ ? ‘R’ : ‘L’] = cell  
cell[v] = h  
end

tape[:C] = ‘\_’  
ARGV[1].to\_s.split(//).reverse.each{|c|tape=tape[‘L’];tape[:C]=c}

until instructions[[state,tape[:C]]].nil?  
state, ch, move = instructions[[state,tape[:C]]]  
tape[:C] = ch  
tape = tape[move]  
end

tape = tape[‘L’] while tape.keys.include? ‘L’  
output = [tape[:C]]  
(tape = tape[‘R’]; output \<\< tape[:C]) while tape.keys.include? ‘R’

puts output.reject{|c|c==‘\_’}.join

----- Original Message ----  
From: Matthew M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
To: ruby-talk ML [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
Sent: Friday, May 9, 2008 10:48:40 AM  
Subject: [QUIZ] The Turing Machine (#162)

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

The three rules of Ruby Q. 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 Q. 2 by submitting ideas as often as you can! (A  
permanent, new website is in the works for Ruby Q. 2. Until then,  
please visit the temporary website at

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem  
helps everyone on Ruby T. follow the discussion. Please reply to  
the original quiz message, if you can.

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

## The Turing Machine

_Quiz description by James Edward G. 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

```