Машина Тьюринга

 

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