Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [QUIZ] The Turing Machine (#162)

Reply
Thread Tools

[QUIZ] The Turing Machine (#162)

 
 
Chris Shea
Guest
Posts: n/a
 
      05-11-2008
On May 10, 10:20 pm, Matthew Moss <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
ThoML
Guest
Posts: n/a
 
      05-11-2008
> I've started on a DSL for creating Turing machine code.

Yummy. Please share.

> http://pastie.textmate.org/195072


Cool.
 
Reply With Quote
 
 
 
 
Chris Shea
Guest
Posts: n/a
 
      05-11-2008
On May 11, 2:14 am, ThoML <(E-Mail Removed)> 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
 
Reply With Quote
 
Chris Carter
Guest
Posts: n/a
 
      05-11-2008
On Sat, May 10, 2008 at 11:20 PM, Matthew Moss <(E-Mail Removed)> 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

 
Reply With Quote
 
Chris Shea
Guest
Posts: n/a
 
      05-11-2008
On May 9, 9:48 am, Matthew Moss <(E-Mail Removed)> 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
 
Reply With Quote
 
ThoML
Guest
Posts: n/a
 
      05-11-2008
> 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
 
Reply With Quote
 
Chris Carter
Guest
Posts: n/a
 
      05-11-2008
> 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

 
Reply With Quote
 
Sandro Paganotti
Guest
Posts: n/a
 
      05-11-2008
This is my solution, I tried to keep it clean (also if I found quite
hard implement the Tape model)

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

On Sun, May 11, 2008 at 5:31 PM, Chris Carter <(E-Mail Removed)> 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!

 
Reply With Quote
 
Andrew Thompson
Guest
Posts: n/a
 
      05-11-2008
I didn't really know what the hell a turing machine actually was until I
read up on it for this quiz but I had fun implementing one:

http://eagle.bsd.st/~andrew/turing.rb

Andrew

--
Posted via http://www.ruby-forum.com/.

 
Reply With Quote
 
Jesús Gabriel y Galán
Guest
Posts: n/a
 
      05-11-2008
On Fri, May 9, 2008 at 5:48 PM, Matthew Moss <(E-Mail Removed)> 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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[SUMMARY] The Turing Machine (#162) Matthew Moss Ruby 4 05-16-2008 07:15 PM
Programming a Turing Machine roxorsoxor2345 C++ 1 12-15-2006 05:47 PM
Turing machine Kvele C Programming 3 01-07-2005 03:23 AM
C++ Simulator of a Universal Turing Machine Alex Vinokur C++ 0 12-19-2003 05:24 AM
C++ Simulator of a Nondeterministic Turing Machine Alex Vinokur C++ 0 11-12-2003 06:47 PM



Advertisments