[QUIZ] The Turing Machine (#162)

M

Matthew Moss

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

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
 
C

Chris Shea

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

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
Click to expand...

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
 
A

Adam Shelly

I created another program for our Turning machines that reverses a
string of zeros and ones. ...
I hope others share some.
Click to expand...
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
 
C

Chiyuan Zhang

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

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

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
Click to expand...
 
J

James Gray

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

Correct, the tape moves with each instruction.

James Edward Gray II
 
G

Glen F. Pankow

Chris said:
... I hope others share some.
Click to expand...

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
 
J

Juanger

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 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?
Click to expand...

Correct, the tape moves with each instruction.

James Edward Gray II
Click to expand...


--=20
Ash Mac durbatul=FBk, ash Mac gimbatul, ash Mac thrakatul=FBk agh burzum-is=
hi
krimpatul.
Juanger.
 
A

Adam Shelly

Below is a (very ugly) machine to convert binary to octal,
since it seems binary is the popular test representation.
Click to expand...
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
 
M

Matthew Moss

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. ;)
 
C

Chris Shea

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. ;)
Click to expand...

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
 
C

Chris Shea

Yummy. Please share.
Click to expand...

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
 
C

Chris Carter

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.
Click to expand...

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
 
C

Chris Shea

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

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
Click to expand...

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
 
T

ThoML

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
 
J

Jesús Gabriel y Galán

## 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.
Click to expand...

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Turing Quine. 0
[SUMMARY] The Turing Machine (#162) 4
Programming a Turing Machine 1
[QUIZ] Distinct Sets (#225) 19
Needing Help! 1
Drawing missing in bitmap in a pure C win32 program 4
[QUIZ] Twitter Personalities (#208) 21
[QUIZ] Plot the Shape (#211) 5

Members online

No members online now.
Total: 38 (members: 0, guests: 38)
Robots: 649

Forum statistics

Threads
473,769
Messages
2,569,581
Members
45,057
Latest member
KetoBeezACVGummies

Latest Threads

Top