base10-multiply.tm

It's easy to see that Turing machines do very well utilizing unary numbers,
but I find them to be very annoying to decode by sight, and not very useful.
To compensate, I wrote a Turing program to convert unary numbers to base10:

	# Starting with nothing is a special case
	Start _ End     0 R
	Start 1 NoMoveA 1 R
	NoMoveA 1 A 1 L
	NoMoveA _ A _ L

	# head is on input.  is anything left?
	A _ End _ R
	A 1 B   1 R

	# head is on start of input.  seek to the end
	B 1 B 1 R
	B _ C _ L

	# head is at end of input.  decrement.
	C 1 D _ L

	# head is at end of input.  seek to start.
	D 1 D 1 L
	D _ E _ L

	# head is at end of output.  increment.
	E _ F 1 R
	E 0 F 1 R
	E 1 F 2 R
	E 2 F 3 R
	E 3 F 4 R
	E 4 F 5 R
	E 5 F 6 R
	E 6 F 7 R
	E 7 F 8 R
	E 8 F 9 R
	E 9 E 0 L

	# head is somewhere in output.  seek right.
	F 0 F 0 R
	F 1 F 1 R
	F 2 F 2 R
	F 3 F 3 R
	F 4 F 4 R
	F 5 F 5 R
	F 6 F 6 R
	F 7 F 7 R
	F 8 F 8 R
	F 9 F 9 R
	F _ A _ R

and a Turing program to convert base10 numbers to unary:

	# Head is at start of input; seek to end
	A 0 A 0 R
	A 1 A 1 R
	A 2 A 2 R
	A 3 A 3 R
	A 4 A 4 R
	A 5 A 5 R
	A 6 A 6 R
	A 7 A 7 R
	A 8 A 8 R
	A 9 A 9 R
	A _ B _ L

	# head is at end of input; decrement
	B 9 C 8 R
	B 8 C 7 R
	B 7 C 6 R
	B 6 C 5 R
	B 5 C 4 R
	B 4 C 3 R
	B 3 C 2 R
	B 2 C 1 R
	B 1 C 0 R
	B 0 B 9 L
	B _ Y _ R	# we've reached zero

	# head is in input; seek right
	C _ D _ R
	C 0 C 0 R
	C 1 C 1 R
	C 2 C 2 R
	C 3 C 3 R
	C 4 C 4 R
	C 5 C 5 R
	C 6 C 6 R
	C 7 C 7 R
	C 8 C 8 R
	C 9 C 9 R

	# head is at start of output; increment
	D 1 D 1 R
	D _ E 1 R

	# head is at blank after output; move to output
	E _ F _ L

	# head is at end of output; seek left to input
	F 1 F 1 L
	F _ B _ L

	# head is at start of input
	Y 9 Y _ R
	Y _ Z _ R

Utilizing these routines, I then wrote base10-multiply.tm.  It accepts
as input two base10 numbers, converts them to two unary numbers, performs
urinary multiplication in a manner similar to the multiplication program
which appeared in the quiz announcement, and then converts the output back
to base10:

	### Stage 0: Validate first input

	# head is at start of first input
	A0 0 B0 0 R # zero
	A0 _ A7 _ R # no argument
	A0 1 A1 1 R
	A0 2 A1 2 R
	A0 3 A1 3 R
	A0 4 A1 4 R
	A0 5 A1 5 R
	A0 6 A1 6 R
	A0 7 A1 7 R
	A0 8 A1 8 R
	A0 9 A1 9 R

	# head is in first input.  seek right and erase
	B0 0 B0 _ R
	B0 1 B0 _ R
	B0 2 B0 _ R
	B0 3 B0 _ R
	B0 4 B0 _ R
	B0 5 B0 _ R
	B0 6 B0 _ R
	B0 7 B0 _ R
	B0 8 B0 _ R
	B0 _ C0 _ R

	# head is at start of second input.  seek right erase.
	C0 0 C0 _ R
	C0 1 C0 _ R
	C0 2 C0 _ R
	C0 3 C0 _ R
	C0 4 C0 _ R
	C0 5 C0 _ R
	C0 6 C0 _ R
	C0 7 C0 _ R
	C0 8 C0 _ R
	C0 9 C0 _ R
	C0 _ End _ R

	### Stage 1: Convert first input from base10 to base1

	# head is at start of first input.  seek to end
	A1 0 A1 0 R
	A1 1 A1 1 R
	A1 2 A1 2 R
	A1 3 A1 3 R
	A1 4 A1 4 R
	A1 5 A1 5 R
	A1 6 A1 6 R
	A1 7 A1 7 R
	A1 8 A1 8 R
	A1 9 A1 9 R
	A1 _ B1 _ L

	# head is at end of first input.  decrement
	B1 9 C1 8 R
	B1 8 C1 7 R
	B1 7 C1 6 R
	B1 6 C1 5 R
	B1 5 C1 4 R
	B1 4 C1 3 R
	B1 3 C1 2 R
	B1 2 C1 1 R
	B1 1 C1 0 R
	B1 0 B1 9 L
	B1 _ H1 _ R	# reached zero

	# head is in first input.  seek right
	C1 _ D1 _ R
	C1 0 C1 0 R
	C1 1 C1 1 R
	C1 2 C1 2 R
	C1 3 C1 3 R
	C1 4 C1 4 R
	C1 5 C1 5 R
	C1 6 C1 6 R
	C1 7 C1 7 R
	C1 8 C1 8 R
	C1 9 C1 9 R

	# head is at start of first input.  seek right
	D1 _ E1 _ R
	D1 0 D1 0 R
	D1 1 D1 1 R
	D1 2 D1 2 R
	D1 3 D1 3 R
	D1 4 D1 4 R
	D1 5 D1 5 R
	D1 6 D1 6 R
	D1 7 D1 7 R
	D1 8 D1 8 R
	D1 9 D1 9 R

	# head is at start of first output.  increment.
	E1 1 E1 1 R
	E1 _ F1 1 L

	# head is in first output.  seek left
	F1 1 F1 1 L
	F1 _ G1 _ L

	# head is at end of second input.  seek left.
	G1 0 G1 0 L
	G1 1 G1 1 L
	G1 2 G1 2 L
	G1 3 G1 3 L
	G1 4 G1 4 L
	G1 5 G1 5 L
	G1 6 G1 6 L
	G1 7 G1 7 L
	G1 8 G1 8 L
	G1 9 G1 9 L
	G1 _ B1 _ L

	# head is at zeroed first input.  erase, and seek right.
	H1 9 H1 _ R
	H1 _ A2 _ R

	### Stage 2: Validate second input

	# head is at start of second input.  check for zero
	A2 0 B0 0 R # zero
	A2 _ A7 _ R # no argument
	A2 1 A3 1 R
	A2 2 A3 2 R
	A2 3 A3 3 R
	A2 4 A3 4 R
	A2 5 A3 5 R
	A2 6 A3 6 R
	A2 7 A3 7 R
	A2 8 A3 8 R
	A2 9 A3 9 R

	### Stage 3: Convert second input from base10 to base1

	# head is at start of second input.  seek to end
	A3 0 A3 0 R
	A3 1 A3 1 R
	A3 2 A3 2 R
	A3 3 A3 3 R
	A3 4 A3 4 R
	A3 5 A3 5 R
	A3 6 A3 6 R
	A3 7 A3 7 R
	A3 8 A3 8 R
	A3 9 A3 9 R
	A3 _ B3 _ L

	# head is at end of input.  decrement
	B3 9 C3 8 R
	B3 8 C3 7 R
	B3 7 C3 6 R
	B3 6 C3 5 R
	B3 5 C3 4 R
	B3 4 C3 3 R
	B3 3 C3 2 R
	B3 2 C3 1 R
	B3 1 C3 0 R
	B3 0 B3 9 L
	B3 _ Z3 _ R	# reached zero

	# head is in input.  seek right
	C3 _ D3 _ R
	C3 0 C3 0 R
	C3 1 C3 1 R
	C3 2 C3 2 R
	C3 3 C3 3 R
	C3 4 C3 4 R
	C3 5 C3 5 R
	C3 6 C3 6 R
	C3 7 C3 7 R
	C3 8 C3 8 R
	C3 9 C3 9 R

	# head is in first output.  seek to end.
	D3 1 D3 1 R
	D3 _ E3 _ R

	# head is at start of second output.  increment.
	E3 1 E3 1 R
	E3 _ F3 1 L

	# head is in second output.  seek left.
	F3 1 F3 1 L
	F3 _ G3 _ L

	# head is at end of first output.  seek left.
	G3 1 G3 1 L
	G3 _ B3 _ L

	# head is at start of zeroed input.  seek right to output.
	Z3 9 Z3 _ R
	Z3 _ A4 _ R

	### Stage 4: Multiply base1 inputs

	# head is at start of converted input.  decrement.
	A4 _ A5 _ L  # nothing left of first input
	A4 X A4 X R
	A4 1 B4 X R

	# head is in first input.  seek to end.
	B4 1 B4 1 R
	B4 _ C4 _ R

	# head is at start of second input.  find next bit to copy.
	C4 X C4 X R
	C4 _ H4 _ L #end
	C4 1 D4 X R

	# head is in second input.  seek to the end.
	D4 1 D4 1 R
	D4 _ E4 _ R

	# head is at start of output.  increment.
	E4 1 E4 1 R
	E4 _ F4 1 L

	# head is in output.  seek left.
	F4 1 F4 1 L
	F4 _ G4 _ L

	# head is at end of second input.  seek left.
	G4 1 G4 1 L
	G4 X G4 X L
	G4 _ C4 _ R

	# head is at end of finished second output.  erase and seek left.
	H4 X H4 1 L
	H4 _ I4 _ L

	# head is at end of first input.  seek left.
	I4 1 I4 1 L
	I4 X I4 X L
	I4 _ A4 _ R

	### Stage 5: Erase inputs

	# head is at end of first argument.  zero it out.
	A5 X A5 _ L
	A5 _ B5 _ R

	# head is somewhere before second argument.  seek right.
	B5 _ B5 _ R
	B5 1 C5 _ R

	# head is before second argument.  zero it out.
	C5 1 C5 _ R
	C5 _ A6 _ R

	### Stage 6: Convert base1 output to base10

	# head is on input.
	A6 _ End _ R
	A6 1 B6  1 R

	# head is on start of input.  seek to the end
	B6 1 B6 1 R
	B6 _ C6 _ L

	# head is at end of input.  decrement.
	C6 1 D6 _ L

	# head is at end of input.  seek to start.
	D6 1 D6 1 L
	D6 _ E6 _ L

	# head is at end of output.  increment.
	E6 _ F6 1 R
	E6 0 F6 1 R
	E6 1 F6 2 R
	E6 2 F6 3 R
	E6 3 F6 4 R
	E6 4 F6 5 R
	E6 5 F6 6 R
	E6 6 F6 7 R
	E6 7 F6 8 R
	E6 8 F6 9 R
	E6 9 E6 0 L

	# head is somewhere in output.  seek right.
	F6 0 F6 0 R
	F6 1 F6 1 R
	F6 2 F6 2 R
	F6 3 F6 3 R
	F6 4 F6 4 R
	F6 5 F6 5 R
	F6 6 F6 6 R
	F6 7 F6 7 R
	F6 8 F6 8 R
	F6 9 F6 9 R
	F6 _ A6 _ R

	### Stage 7: Error messages

	# head is at start of something.  clean to end.
	A7 0 A7 _ R
	A7 1 A7 _ R
	A7 2 A7 _ R
	A7 3 A7 _ R
	A7 4 A7 _ R
	A7 5 A7 _ R
	A7 6 A7 _ R
	A7 7 A7 _ R
	A7 8 A7 _ R
	A7 9 A7 _ R
	A7 _ B7 _ L

	B7 _ C7  U R
	C7 _ D7  s R
	D7 _ E7  a R
	E7 _ F7  g R
	F7 _ G7  e R
	G7 _ H7  _ R
	H7 _ I7  n R
	I7 _ J7  u R
	J7 _ K7  m R
	K7 _ L7  _ R
	L7 _ M7  n R
	M7 _ N7  u R
	N7 _ End m R

-mct

-- 
perl -e'$u="\4\5\6";sub H{8*($_[1]%79)+($_[0]%8)}sub G{vec$u,H(@_),1}sub S{vec
($n,H(@_),1)=$_[2]}$_=q^{P`clear`;for$iX){PG($iY)?"O":" "forX8);P"\n"}for$iX){
forX8){$c=scalar grep{G@$_}[$i-1Y-1Z-1YZ-1Y+1ZY-1ZY+1Z+1Y-1Z+1YZ+1Y+1];S$iY,G(
$iY)?$c=~/[23]/?1:0:$c==3?1:0}}$u=$n;select$M,$C,$T,.2;redo}^;s/Z/],[\$i/g;s/Y
/,\$_/xg;s/X/(0..7/g;s/P/print+/g;eval' #     Michael C. Toren <[email protected]>