Binary addition for Turing Machine simulator

Perhaps someone can use this as a subroutine to put together a 
multiplication program.
To add 6 and 11, use

	perl tm.pl addition.tm 110_1011

which then outputs

	10001


I had forgotten how tedious it is to write these things.
It's almost impossible to do it without thinking about writing a 
compiler instead.
It would be very easy to extend the input language to support

	statename STEP LEFT THEN otherstate

which would abbreviate

	statename _ otherstate _ L
	statename 0 otherstate 0 L
	statename 1 otherstate 1 L
	...
	statename z otherstate z L

or one could add:

	statename SEEK RIGHT TO 0 THEN otherstate

which would abbreviate

	statename _ statename _ R
	statename 0 gen00127 0 R
	statename 1 statename 1 R
	...
	statename z otherstate z R
	gen00127 STEP LEFT THEN otherstate


Anyway, here is the adder.  I have tested it with all combinations of 
inputs up to 4 bits long, so I think it works correctly.


# The head is positioned at the leftmost addend digit
# Seek to space past addend
Amr0 1 Amr0 1 R
Amr0 0 Amr0 0 R
Amr0 X Amr0 X R
Amr0 _ Bmr0 _ R

Amr1 1 Amr1 1 R
Amr1 0 Amr1 0 R
Amr1 X Amr1 X R
Amr1 _ Bmr1 _ R

# The head is positioned at the leftmost augend digit
# Seek to the rightmost augend digit
Bmr0 0 Bmr0 0 R
Bmr0 1 Bmr0 1 R
Bmr0 X GB0  X L
Bmr0 _ GB0  _ L

Bmr1 0 Bmr1 0 R
Bmr1 1 Bmr1 1 R
Bmr1 X GB1  X L
Bmr1 _ GB1  _ L

# The head is either at the rightmost augend digit
# or it is in the separator
GB0 0 Bml0 X L
GB0 1 Bml1 X L
GB0 _ AXl0 _ L

GB1 0 Bml1 X L
GB1 1 Bml2 X L
GB1 _ AXl1 _ L

# Move left past the augend and the separator
Bml0 0 Bml0 0 L
Bml0 1 Bml0 1 L
Bml0 _ Aml0 _ L

Bml1 0 Bml1 0 L
Bml1 1 Bml1 1 L
Bml1 _ Aml1 _ L

Bml2 0 Bml2 0 L
Bml2 1 Bml2 1 L
Bml2 _ Aml2 _ L

# Find the rightmost digit of the addend and erase it
Aml0 0 Asl0 X L
Aml0 1 Asl1 X L
Aml0 X Aml0 X L
Aml0 _ Csl0 _ L

Aml1 0 Asl1 X L
Aml1 1 Asl2 X L
Aml1 X Aml1 X L
Aml1 _ Csl1 _ L

Aml2 0 Asl2 X L
Aml2 1 Asl3 X L
Aml2 X Aml2 X L
Aml2 _ Csl2 _ L

# Skip left past the rest of the addend
Asl0 0 Asl0 0 L
Asl0 1 Asl0 1 L
Asl0 _ Csl0 _ L

Asl1 0 Asl1 0 L
Asl1 1 Asl1 1 L
Asl1 _ Csl1 _ L

Asl2 0 Asl2 0 L
Asl2 1 Asl2 1 L
Asl2 _ Csl2 _ L

Asl3 0 Asl3 0 L
Asl3 1 Asl3 1 L
Asl3 _ Csl3 _ L

# Skip left past the sum and write the sum digit
Csl0 0 Csl0 0 L
Csl0 1 Csl0 1 L
Csl0 _ CLl0 0 L

Csl1 0 Csl1 0 L
Csl1 1 Csl1 1 L
Csl1 _ CLl0 1 L

Csl2 0 Csl2 0 L
Csl2 1 Csl2 1 L
Csl2 _ CLl1 0 L

Csl3 0 Csl3 0 L
Csl3 1 Csl3 1 L
Csl3 _ CLl1 1 L

# Now the head is to the left of the sum.  Move right one space
CLl0 _ Cmr0 _ R
CLl1 _ Cmr1 _ R

# The head is at the leftmost digit of the sum.  Locate the addend
Cmr0 0 Cmr0 0 R
Cmr0 1 Cmr0 1 R
Cmr0 _ Amr0 _ R

Cmr1 0 Cmr1 0 R
Cmr1 1 Cmr1 1 R
Cmr1 _ Amr1 _ R

# The following is the ending routine, reached when the augend is
# exhausted.  The head is at the rightmost digit of the addend.
# Scan left past Xes.
# If we find a digit, erase it and continue as usual.
# If not, the addend is exhausted as well.
AXl0 0 Asl0 X L
AXl0 1 Asl1 X L
AXl0 X AXl0 X L
AXl0 _ FINA _ R

AXl1 0 Asl1 X L
AXl1 1 Asl2 X L
AXl1 X AXl1 X L
AXl1 _ AEl1 _ L

# The head is at the rightmost digit of the sum; we have another 1
# left to write at the left end
AEl1 0 AEl1 0 L
AEl1 1 AEl1 1 L
AEl1 _ FINC 1 R

FINC 0 FINC 0 R
FINC 1 FINC 1 R
FINC _ FINA _ R

FINA X FINA _ R
FINA _ FINB _ R

FINB X FINB _ R
FINB _ HALT _ R