Re: [SPOILER] Perl Quiz of the Week #24 (Turing Machine simulation)

Bill Tucker wrote:
> I was a little surprised at how easy this was. I'd studied Turing 
> machines in school, but had never actually implemented one.

Same here.  When I was in school I thought about implementing
one but all I knew at that time was Basic, C, and Pascal -- none
of which supported dictionaries as a standard data type.

My code (in Python) is essentially the same as yours except I
use a dictionary for the tape rather than a list.

I just waste^H^H^H^H^Hspent the last 5 hours or so implementing
a stack interpreter for the Turing Machine Instruction Set.  It
uses unary numbers, so
   0 ==
   1 == 1
   2 == 11
   5 == 11111
    etc.
It does not understand negative numbers.

The stack commands are:

  1 - part of a number (ignore and move right to next character)
  P - push a number on the stack (must use this after you enter a number)
  A - replace top two numbers in stack with their sum
  D - duplicate top element of stack
  I - pop top element
  N - null operation
  M - replace top two numbers with their product
  S - replace top two numbers in stack with value of 2nd minus 1st
        (so '1111P1PS' is '111'). If <0 use 0.

Here are some examples of use

    # addition
% python ./turing.py stackm.tm '1111P1PA'
11111
    # subtraction
% python ./turing.py stackm.tm '1111P1PS'
111
    # multiplication
% python ./turing.py stackm.tm '1111P11PM'
11111111
    # duplicate stack (0 is used to separate numbers)
% python ./turing.py stackm.tm '1111P11PMD'
11111111011111111
    # 4 2 * dup * == 8*8 == 64
% python ./turing.py stackm.tm '1111P11PMDM'
1111111111111111111111111111111111111111111111111111111111111111
    # multiply by 0 works
% python ./turing.py stackm.tm '111PPM'
    # 2**5
% python ./turing.py stackm.tm '11PDDDDMMMM'
11111111111111111111111111111111

(Interesting.  I should be able to implement exponentiation
using the same sort of trick I used to implement multiplication.)

The pop and no-op were used to make it easier to implement
the multiplication code.  I won't show examples here.

Next, a swap, and a rotate 3, and support for negative numbers,
and ... why soon I'll have a Forth interpreter!

Code is at the end of this email.  I'm not sure I'll be able
to remember how it works come the morning.  :)

					Andrew
					dalke-DxsMES/F/[email protected]

# 1 - part of a number
# P - push
# A - add top two elements in stack
# D - duplicate top
# I - pop ...
# N - nullop
# M - multiply
# S - subtract (negative numbers not supported)

# use 0 to separate numbers on the stack

# Seek right for the next command
seekcmd 1 seekcmd   1 R  # skip 1s
seekcmd P seekcmd   0 R  # push? that was easy
seekcmd A add X L  # new end of stack; mark X for execution point
seekcmd D dup X L  # duplicate top of stack
seekcmd I pop X L # pop top of stack
seekcmd N nullop X L # null operation
seekcmd M mult X L # multiply
seekcmd S sub X L # subtract

# Get rid of the final 0, which indicates the number on the stack
seekcmd _ clean_stack _ L
clean_stack 0 end _ L

############

# How to add:
#  go left to the second 0
#  mark it with an 'X'
#  go left to the end
#  copy from there one to the left, until the X is reached
#  go left to the end
#  copy from there one to the left, until the X is reached
#  look for the next instruction

# The first character must be the '0'
add 0 add_find_2nd_0 0 L

add_find_2nd_0 1 add_find_2nd_0 1 L
add_find_2nd_0 0 add_seek_left_end X L

##### Move everything left of the X one character to the right
#  This does the add

add_seek_left_end 0 add_seek_left_end 0 L
add_seek_left_end 1 add_seek_left_end 1 L
add_seek_left_end _ add_copy__right _ R

add_copy__right 0 add_copy0_right _ R
add_copy1_right 0 add_copy0_right 1 R
add_copy0_right 0 add_copy0_right 0 R

add_copy__right 1 add_copy1_right _ R
add_copy1_right 1 add_copy1_right 1 R
add_copy0_right 1 add_copy1_right 0 R

add_copy__right X rm_instruction _ R
add_copy1_right X rm_instruction 1 L
add_copy0_right X rm_instruction 0 L

## move everything right again to remove the 'X'
## instruction from the stack ('X' replaced the current command)
rm_instruction 0 rm_instruction 0 L
rm_instruction 1 rm_instruction 1 L
rm_instruction X rm_instruction X L
rm_instruction _ rm_copy__right _ R

rm_copy__right 0 rm_copy0_right _ R
rm_copy1_right 0 rm_copy0_right 1 R
rm_copy0_right 0 rm_copy0_right 0 R

rm_copy__right 1 rm_copy1_right _ R
rm_copy1_right 1 rm_copy1_right 1 R
rm_copy0_right 1 rm_copy1_right 0 R

rm_copy__right X seekcmd _ R
rm_copy1_right X seekcmd 1 R
rm_copy0_right X seekcmd 0 R



#### duplicate top of stack
# Find the region to copy.  Either to the _ or to the 0
dup 0 dup_left_side 0 L     # must be a 0
dup_left_side 1 dup_left_side 1 L  # find the _ or next 0
dup_left_side _ dup_find1 X R
dup_left_side 0 dup_copy0_left X L  # insert a 0 here

# Where's the next 1 to copy?
dup_find1 A dup_find1 A R
dup_find1 1 dup_need1 A L
dup_find1 0 dup_cleanup 0 L

dup_need1 A dup_need1 A L
dup_need1 X dup_copy1_left X L

dup_copy1_left 0 dup_copy0_left 1 L
dup_copy1_left 1 dup_copy1_left 1 L
dup_copy1_left _ dup_goto_mark 1 R

dup_copy0_left 0 dup_copy0_left 0 L
dup_copy0_left 1 dup_copy1_left 0 L
dup_copy0_left _ dup_goto_mark 0 R

dup_goto_mark 0 dup_goto_mark 0 R
dup_goto_mark 1 dup_goto_mark 1 R
dup_goto_mark X dup_find1 X R


dup_cleanup A dup_cleanup 1 L
dup_cleanup X rm_instruction 0 L  # all done!


## pop

# First delete the 0

# Go to the far left
pop 0 pop_seek_left0 0 L  # Make sure there's a 0 here

pop_seek_left0 0 pop_seek_left0 0 L
pop_seek_left0 1 pop_seek_left0 1 L
pop_seek_left0 _ pop_copy__right0 _ R

# and copy right until we've replaced the 0
pop_copy__right0 0 pop_copy0_right0 _ R
pop_copy1_right0 0 pop_copy0_right0 1 R
pop_copy0_right0 0 pop_copy0_right0 0 R

pop_copy__right0 1 pop_copy1_right0 _ R
pop_copy1_right0 1 pop_copy1_right0 1 R
pop_copy0_right0 1 pop_copy1_right0 0 R

# ah-ha, we're back to the exectution point
# delete 1s until they are gone
pop_copy0_right0 X pop_check_1 X L

pop_check_1 1 pop_seek_left 1 L
pop_seek_left 0 pop_seek_left 0 L
pop_seek_left 1 pop_seek_left 1 L
pop_seek_left _ pop_copy__right1 _ R

pop_copy__right1 0 pop_copy0_right1 _ R
pop_copy1_right1 0 pop_copy0_right1 1 R
pop_copy0_right1 0 pop_copy0_right1 0 R

pop_copy__right1 1 pop_copy1_right1 _ R
pop_copy1_right1 1 pop_copy1_right1 1 R
pop_copy0_right1 1 pop_copy1_right1 0 R

# ah-ha, we've deleted the 1.
# Check for another one
pop_copy1_right1 X pop_check_1 X L

pop_check_1 0 rm_instruction 0 R
pop_check_1 _ rm_instruction _ R

#####
nullop 0 nullop 0 L
nullop 1 nullop 1 L
nullop _ nullop_copy__right _ R

nullop_copy__right 0 nullop_copy0_right _ R
nullop_copy1_right 0 nullop_copy0_right 1 R
nullop_copy0_right 0 nullop_copy0_right 0 R

nullop_copy__right 1 nullop_copy1_right _ R
nullop_copy1_right 1 nullop_copy1_right 1 R
nullop_copy0_right 1 nullop_copy1_right 0 R

nullop_copy0_right X seekcmd 0 R
nullop_copy1_right X seekcmd 0 R


#####
# Multiplication
# Check for multiply by 0

mult 0 mult_by0_check 0 L
mult_by0_check 0 mult_by0_seek_left 0 L
mult_by0_check 1 mdup 1 R

# Multiplication by 0
# Mult by 0 is the same as as doing two pops
# Stack looks like

# ...00X...
#     ^
# Want to remove the 0 next to the X then do a pop

mult_by0_seek_left 0 mult_by0_seek_left 0 L
mult_by0_seek_left 1 mult_by0_seek_left 1 L
mult_by0_seek_left _ mult_by0_copy__right _ R

mult_by0_copy__right 0 mult_by0_copy0_right _ R
mult_by0_copy1_right 0 mult_by0_copy0_right 1 R
mult_by0_copy0_right 0 mult_by0_copy0_right 0 R

mult_by0_copy__right 1 mult_by0_copy1_right _ R
mult_by0_copy1_right 1 mult_by0_copy1_right 1 R
mult_by0_copy0_right 1 mult_by0_copy1_right 0 R

mult_by0_copy0_right X pop X L

#### Here's how to multiply -- can be made faster, but this works

#  .......1011110M
#  .......1011110X       # do a stack dup, terminate with nullop
#               ^
#  .......101111011110N  # replace leftwards with two nullops
#                    ^
#  .......1011110111NNN  #
#                  ^
#  .......1011110111NNN  # replace 1s leftwards with As
#  .......1011110AAANNN  # replace leftwards with two nullops
#               ^
#  .......10111NNAAANNN  # replace leftwards with Ds
#             ^
#  .......10DDDNNAAANNN  # go forward one ...
#          ^
#  .......10DDDNNAAANNN  # ... and execute
#           ^

# ### This is a copy of the 'dup' code
mdup 0 mdup_left_side 0 L     # must be a 0
mdup_left_side 1 mdup_left_side 1 L  # find the _ or next 0
mdup_left_side _ mdup_find1 X R
mdup_left_side 0 mdup_copy0_left X L  # insert a 0 here

# Where's the next 1 to copy?
mdup_find1 A mdup_find1 A R
mdup_find1 1 mdup_need1 A L
mdup_find1 0 mdup_cleanup 0 L

mdup_need1 A mdup_need1 A L
mdup_need1 X mdup_copy1_left X L

mdup_copy1_left 0 mdup_copy0_left 1 L
mdup_copy1_left 1 mdup_copy1_left 1 L
mdup_copy1_left _ mdup_goto_mark 1 R

mdup_copy0_left 0 mdup_copy0_left 0 L
mdup_copy0_left 1 mdup_copy1_left 0 L
mdup_copy0_left _ mdup_goto_mark 0 R

mdup_goto_mark 0 mdup_goto_mark 0 R
mdup_goto_mark 1 mdup_goto_mark 1 R
mdup_goto_mark X mdup_find1 X R


mdup_cleanup A mdup_cleanup 1 L
mdup_cleanup X mult_find_right_1stX X L  # did the dup

mult_find_right_1stX 0 mult_find_right_1stX 0 R
mult_find_right_1stX 1 mult_find_right_1stX 1 R
mult_find_right_1stX X mult_find_right_2ndX X R

mult_find_right_2ndX 0 mult_find_right_2ndX 0 R
mult_find_right_2ndX 1 mult_find_right_2ndX 1 R
mult_find_right_2ndX X multi_place_nullop1 N L

multi_place_nullop1 0 multi_place_nullop2 N L
multi_place_nullop2 1 multi_fill_with_As N L

multi_fill_with_As 1 multi_fill_with_As A L
multi_fill_with_As X multi_fill_with_nullop4 N L
multi_fill_with_nullop4 1 multi_fill_with_Ds N L

multi_fill_with_Ds 1 multi_fill_with_Ds D L
multi_fill_with_Ds 0 seekcmd 0 R

### subtraction
# remove one digit from both previous numbers on the stack
# continue until one of the numbers is depleted
# replace the X with an I (pop) and reexecute
#   ..... 2nd 1st <subtract> ...
sub 0 sub_check_1st_nonzero 0 L

sub_check_1st_nonzero 1 sub_find_2nd X L  # note marker placed here!
sub_check_1st_nonzero 0 sub_do_pop 0 R   # first number is 0

sub_find_2nd 1 sub_find_2nd 1 L
sub_find_2nd 0 sub_check_2nd_nonzero 0 L

sub_check_2nd_nonzero 1 sub_find_left X L  # note marker placed here!
sub_check_2nd_nonzero 0 sub_do_pop 0 R   # second number is 0
sub_check_2nd_nonzero _ sub_do_pop _ R   # second number is 0

sub_find_left 1 sub_find_left 1 L
sub_find_left 0 sub_find_left 0 L
sub_find_left _ sub_copy__right_2nd _ R

sub_copy__right_2nd 0 sub_copy0_right_2nd _ R
sub_copy1_right_2nd 0 sub_copy0_right_2nd 1 R
sub_copy0_right_2nd 0 sub_copy0_right_2nd 0 R

sub_copy__right_2nd 1 sub_copy1_right_2nd _ R
sub_copy1_right_2nd 1 sub_copy1_right_2nd 1 R
sub_copy0_right_2nd 1 sub_copy1_right_2nd 0 R

# Remove the 1 that was under this X
sub_copy__right_2nd X sub_copy__right_1st _ R  # already at left
sub_copy0_right_2nd X sub_find_left_again 0 L
sub_copy1_right_2nd X sub_find_left_again 1 L

sub_find_left_again 0 sub_find_left_again 0 L
sub_find_left_again 1 sub_find_left_again 1 L
sub_find_left_again _ sub_copy__right_1st _ R

sub_copy__right_1st 0 sub_copy0_right_1st _ R
sub_copy1_right_1st 0 sub_copy0_right_1st 1 R
sub_copy0_right_1st 0 sub_copy0_right_1st 0 R

sub_copy__right_1st 1 sub_copy1_right_1st _ R
sub_copy1_right_1st 1 sub_copy1_right_1st 1 R
sub_copy0_right_1st 1 sub_copy1_right_1st 0 R

# Remove the 1 that was under this X then try again
sub_copy__right_1st X sub _ R
sub_copy0_right_1st X sub 0 R
sub_copy1_right_1st X sub 1 R

# Find the execution point X and replace with an I then exec
sub_do_pop 0 sub_do_pop 0 R
sub_do_pop 1 sub_do_pop 1 R
sub_do_pop X sub_exec_pop I L
sub_exec_pop 0 seekcmd 0 R