turing.htm             - описание машины Тьюринга, 

tmmul2.java         - программа удвоения количества единиц на ленте, 

resultmul2.java    - результат суперкомпиляции примера tmmul2.java,

turingmashine.zip - все исходные тексты и результаты суперкомпиляции.

      Классическая задача для суперкомпилятора - превращение интерпретатора в компилятор. На примере машины Тьюринга эта задача решается в полном объеме.

      Любой интерпретатор для любого языка программирования в качестве входных данных получает, во первых, текст интерпретируемой программы и, во вторых, исходные данные для нее.

      Получая текст конкретной программы, суперкомпилятор построит результирующую программу, в которой будут учтены возможные оптимизации, связанные со знанием текста исходной программы.

      Машина Тьюринга была создана в 30-е годы в качестве теоретического механизма для обоснования понятия алгоритма и для доказательства алгоритмической неразрешимости некоторых проблем. Описание одного из возможных вариантов машины мы привели в turing.htm.

      Машина Тьюринга очень просто устроена, поэтому на ее примере полностью решается задача для суперкомпилятора по превращению интерпретатора в компилятор.

      Данная тема весьма благоприятна для всяческих экспериментов с суперкомпилятором по разным причинам. Можно работать с собственными программами для машины Тьюринга. Можно модифицировать предлагаемые здесь интерпретаторы машины Тьюринга.

      Предлагаются три примера программ для машины Тьюринга. 

      Пример 1. tmmul2.java , resultmul2.java. Удвоение количества единиц.

      Пример 2 (div3). turingmashine.zip. Определение остатка от деления на 3 заданного числа (если остаток равен нулю, то число делится на 3). Количество инструкций для машины Тьюринга около 30, объем построенной суперкомпилятором программы - 9 505 б.

      Пример 3 (div9). turingmashine.zip. Определение остатка от деления на 9 заданного числа. Количество инструкций для машины Тьюринга около 100, объем построенной суперкомпилятором программы - 22 900 б.

      В таблице приведены времена в секундах работы программ для этих трех примеров. Длина ленты машины Тьюринга выбиралась из расчета получения не очень большого и не очень маленького времени исполнения.  

 

	mul2	div3	div9
без параметра -Xint
до суперкомпиляции	2.093	0.231	0.631
после суперкомпиляции	0.51	0.101	0.321
коэффициент ускорения	4.10	2.29	1.97
с параметром -Xint
до суперкомпиляции	17.636	1.602	4.767
после суперкомпиляции	7.08	0.421	1.032
коэффициент ускорения	2.49	3.81	4.62