index.htm - Russian text

turingmachine2.zip  -   all source texts.

The classical task for the supercompiler - transformation of the interpreter in the compiler. On an example of a Turing machine this task is decided in complete size.

Any interpreter for any programming language as input datas receives, in first, text of the interpreted program and, in second, input datas for it.

Receiving the text of the concrete program, the supercompiler can construct the resulting program, in which the possible optimizations, bound with knowledge of the text of the source program will be taken into account.

The Turing machine was set up per 30 years as the theoretical mechanism for the substantiation of concept of algorithm and for the proof of algorithmic insolubility of some problems. The description of one of optional versions of the computer we have reduced in turingeng.htm.

The Turing machine is very simply arranged, therefore on its example the task for the supercompiler on transformation of the interpreter in the compiler is completely decided.

Some example programs for a Turing machine are offered.

Example 1. ( Fab.java , Fab.js ). The simple program of replacement of characters "a" on "b". The program for a Turing machine consists of two instructions

        { "start", "a",  "b",  "start",   "right" },
        { "start", " ",  " ",  "stop",    "left"  }

Which are made out by the way of two-dimensional array String. The program Fab.java exposes to supercompilation which consists of two methods, main and test. In a method main there are initial operations on organization of an initial state of a fillet. Here fillet is set by the string array. It is supercompilation the method test, in which happens interpretation of a Turing machine, given set of the instructions.

The supercompiler creates the program :

//--------------------------------------   0 sec - postprocessing...
	public static void test ()
	{
	  Fab.state = "start";
	  while (Fab.state != "stop") {
	    if (Fab.state == "start"
	    &&  Fab.tape[Fab.head] == "a") {
	      Fab.state = "start";
	      Fab.tape[Fab.head] = "b";
	      Fab.head++;}
	    if (Fab.state == "start"
	    &&  Fab.tape[Fab.head] == " ") {
	      Fab.state = "stop";
	      Fab.tape[Fab.head] = " ";
	      Fab.head--;}
	    continue;}
	  /*while*/
	  return;
	}
//--------------------------------------   0 sec - JScp version 0.0.75

Example 2 ( tmmul2.java , tmmul2.js ). Doubling of an amount of units.

The instructions for a Turing machine

        { "start",  " ",  " ",  "stop" ,  "right" },
        { "start",  "2",  "2",  "start",  "right" },
        { "start",  "1",  "2",  "b"    ,  "left"  },
        { "b"    ,  "2",  "2",  "b"    ,  "left"  },
        { "b"    ,  " ",  "2",  "start",  "right" }

The residual program is completely similar to the previous example - consists of five uniform fragments.

Example 3 ( tmdiv3.java , tmdiv3.js ). Definition of residual from division on 3 given numbers (if the residual is peer to zero, the number is divided on 3).   an amount of the instructions for a Turing machine about 30.

Example 4 (  brackets. java , brackets.js ).  check of parenthesis frame. If parenthesis frame exact, on a fillet the character "1" is written, if incorrect, the character "0" is written.

Example 5 ( delete.java , delete.js ).  space suppression between units. The processed site of a fillet should be framed by characters ".". For example, if in the initial moment on a fillet there were characters  

.1     1     1    .

That in the extremity the fillet will look like

.111.

Example 6 (  multiplication.java , multiplication.js ).   multiplying of two numbers, given in a unary number system. The example is taken without change with http://www.ams.org/new-in-math/cover/turing_multiply_code.html

In the application turingmachine2.zip  all source texts, outcomes of fulfilment of the source programs are located. In the directory Res_Multiplication - fulfilment of the residual program for last example.