/*
Interpreter of the Turing Machine.
An initial CURRENT_STATE of the Turing Machine is coded by "start",
final CURRENT_STATE - by "halt".
The shift of the head to the right is designated through "R",
to the left - through "L" .
*/
class Multiplication {
public static int ltape = 50; /* Length of a tape */
public static int nunits1 = 4; /* It is 3 */
public static int nunits2 = 5; /* It is 4 */
public static int head;
public static String state;
/* Indexes in array of the instructions, */
public static final int CURRENT_STATE = 0;
public static final int CURRENT_SYMBOL = 1;
public static final int NEXT_SYMBOL = 3;
public static final int NEXT_STATE = 2;
public static final int MOVE = 4;
public static String[] tape = new String[ltape];
/*
http://www.ams.org/new-in-math/cover/turing_multiply_code.html
# Turing machine to multiply two numbers:
# Number n is represented by string of n+1 1's.
# Initially, tape is assumed to be in form of _n1_n2_ (where _ is blank),
# and head is assumed to be positioned at leftmost non-blank square.
# Initial internal machine state is "start".
# At halt, tape is _n1_n2_n3_, where n3=n1*n2,
# and head is positioned at leftmost non-blank square.
start, 1, move1right, W, R # mark first bit of 1st argument
move1right, 1, move1right, 1, R # move right til past 1st argument
move1right, _, mark2start, _, R # square between 1st and 2nd arguments found
mark2start, 1, move2right, Y, R # mark first bit of 2nd argument
move2right, 1, move2right, 1, R # move right til past 2nd argument
move2right, _, initialize, _, R # square between 2nd argument and answer found
initialize, _, backup, 1, L # put a 1 at start of answer
backup, _, backup, _, L # move back to leftmost unused bit of 1st arg
backup, 1, backup, 1, L # ditto
backup, Z, backup, Z, L # ditto
backup, Y, backup, Y, L # ditto
backup, X, nextpass, X, R # in position to start next pass
backup, W, nextpass, W, R # ditto
nextpass, _, finishup, _, R # if square is blank, we're done. finish up
nextpass, 1, findarg2, X, R # if square is not blank, go to work. mark bit
findarg2, 1, findarg2, 1, R # move past 1st argument
findarg2, _, findarg2, _, R # square between 1st and 2nd arguments
findarg2, Y, testarg2, Y, R # start of 2nd arg. skip this bit, copy rest
testarg2, _, cleanup2, _, L # if blank, we are done with this pass
testarg2, 1, findans, Z, R # if not, increment ans. mark bit, move there
findans, 1, findans, 1, R # still in 2nd argument
findans, _, atans, _, R # square between 2nd argument and answer
atans, 1, atans, 1, R # move through answer
atans, _, backarg2, 1, L # at end of answer--write a 1 here, go back
backarg2, 1, backarg2, 1, L # move left to first unused bit of 2nd arg
backarg2, _, backarg2, _, L # ditto
backarg2, Z, testarg2, Z, R # just past it. move right, and test it
backarg2, Y, testarg2, Y, R # ditto
cleanup2, 1, cleanup2, 1, L # move back through answer
cleanup2, _, cleanup2, _, L # square between 2nd arg and answer
cleanup2, Z, cleanup2, 1, L # restore bits of 2nd argument
cleanup2, Y, backup, Y, L # done with that. backup to start next pass
finishup, Y, finishup, 1, L # restore first bit of 2nd argument
finishup, _, finishup, _, L # 2nd argument restored, move back to 1st
finishup, X, finishup, 1, L # restore bits of 1st argument
finishup, W, almostdone, 1, L # restore first bit of 1st arg. almost done
almostdone, _, halt, _, R # done with work. position properly and halt
*/
public static final String[][] instruction = {
{ "start", "1", "move1right", "W", "R" },
{ "move1right", "1", "move1right", "1", "R" },
{ "move1right", "_", "mark2start", "_", "R" },
{ "mark2start", "1", "move2right", "Y", "R" },
{ "move2right", "1", "move2right", "1", "R" },
{ "move2right", "_", "initialize", "_", "R" },
{ "initialize", "_", "backup", "1", "L" },
{ "backup", "_", "backup", "_", "L" },
{ "backup", "1", "backup", "1", "L" },
{ "backup", "Z", "backup", "Z", "L" },
{ "backup", "Y", "backup", "Y", "L" },
{ "backup", "X", "nextpass", "X", "R" },
{ "backup", "W", "nextpass", "W", "R" },
{ "nextpass", "_", "finishup", "_", "R" },
{ "nextpass", "1", "findarg2", "X", "R" },
{ "findarg2", "1", "findarg2", "1", "R" },
{ "findarg2", "_", "findarg2", "_", "R" },
{ "findarg2", "Y", "testarg2", "Y", "R" },
{ "testarg2", "_", "cleanup2", "_", "L" },
{ "testarg2", "1", "findans", "Z", "R" },
{ "findans", "1", "findans", "1", "R" },
{ "findans", "_", "atans", "_", "R" },
{ "atans", "1", "atans", "1", "R" },
{ "atans", "_", "backarg2", "1", "L" },
{ "backarg2", "1", "backarg2", "1", "L" },
{ "backarg2", "_", "backarg2", "_", "L" },
{ "backarg2", "Z", "testarg2", "Z", "R" },
{ "backarg2", "Y", "testarg2", "Y", "R" },
{ "cleanup2", "1", "cleanup2", "1", "L" },
{ "cleanup2", "_", "cleanup2", "_", "L" },
{ "cleanup2", "Z", "cleanup2", "1", "L" },
{ "cleanup2", "Y", "backup", "Y", "L" },
{ "finishup", "Y", "finishup", "1", "L" },
{ "finishup", "_", "finishup", "_", "L" },
{ "finishup", "X", "finishup", "1", "L" },
{ "finishup", "W", "almostdone", "1", "L" },
{ "almostdone", "_", "halt", "_", "R" }
};
public static void main (String args[]) {
head = ltape/2; /* the head in the middle of a tape */
for (int i = 0; i < ltape; i++) { /* filling of blank */
tape[i] = "_";
}
for (int i = head; i < head+nunits1; i++) {
tape[i] = "1";
}
for (int i = head+nunits1+1; i < head+nunits1+1+nunits2; i++) {
tape[i] = "1";
}
long start = System.currentTimeMillis();
test();
long end = System.currentTimeMillis();
System.out.println("Total time = "+ (end-start)*0.001);
System.out.println("Final Tape : " );
for (int i = 0; i < ltape; i++)
System.out.print(tape[i]) ;
}
public static void test() {
state = "start";
while (state != "halt") {
for (int i=0; i<instruction.length; i++) {
if (state == instruction[i][CURRENT_STATE]
&& tape[head] == instruction[i][CURRENT_SYMBOL]) {
state=instruction[i][NEXT_STATE];
tape[head]=instruction[i][NEXT_SYMBOL];
if(instruction[i][MOVE]=="R") head++;
if(instruction[i][MOVE]=="L" ) head--;
}
}
}
}
}