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
<mct-ivKz19tO56FeoWH0uzbU5w@xxxxxxxxxxxxxxxx>
|
