index.htm - English text
- все исходные тексты и результаты суперкомпиляции.
Классическая задача для суперкомпилятора - превращение интерпретатора в компилятор. На примере машины Тьюринга эта задача решается в полном объеме.
Любой интерпретатор для любого языка программирования в качестве входных данных получает, во первых, текст интерпретируемой программы и, во вторых, исходные данные для нее.
Получая текст конкретной программы, суперкомпилятор может построить результирующую программу, в которой будут учтены возможные оптимизации, связанные со знанием текста исходной программы.
Машина Тьюринга была создана в 30-е годы в качестве теоретического механизма для обоснования понятия алгоритма и для доказательства алгоритмической неразрешимости некоторых проблем. Описание одного из возможных вариантов машины мы привели в turing.htm.
Машина Тьюринга очень просто устроена, поэтому на ее примере полностью решается задача для суперкомпилятора по превращению интерпретатора в компилятор.
Предлагается несколько примеров программ для машины Тьюринга.
Пример 1. ( Fab.java , Fab.js ). Простая программа замены символов "a" на "b". Программа для машины Тьюринга состоит из двух инструкций
{ "start", "a", "b", "start", "right" },
{ "start", " ", " ", "stop", "left" }
которые оформляются в виде двумерного массива String. Суперкомпиляции подвергается программа Fab.java , которая состоит из двух методов, main и test. В методе main происходят начальные действия по организации начального состояния ленты. Здесь лента задается строковым массивом. Суперкомпилируется метод test, в котором происходит интерпретация машины Тьюринга, заданной набором инструкций.
Суперкомпилятор строит программу Fab.js :
//-------------------------------------- 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
Пример 2 ( tmmul2.java , tmmul2.js ). Удвоение количества единиц.
Инструкции для машины Тьюринга
{ "start", " ", " ", "stop" , "right" },
{ "start", "2", "2", "start", "right" },
{ "start", "1", "2", "b" , "left" },
{ "b" , "2", "2", "b" , "left" },
{ "b" , " ", "2", "start", "right" }
Остаточная программа mmul2.js совершенно аналогична предыдущему примеру - она состоит из пяти единообразных фрагментов.
Пример 3 ( tmdiv3.java , tmdiv3.js ). Определение остатка от деления на 3 заданного числа (если остаток равен нулю, то число делится на 3). Количество инструкций для машины Тьюринга около 30.
Пример 4 ( brackets. java , brackets.js ). Проверка скобочной структуры. Если скобочная структура правильная, то на ленту пишется символ "1", если неправильная, то пишется символ "0".
Пример 5 ( delete.java , delete.js ). Удаление пробелов между единицами. Обрабатываемый участок ленты должен быть обрамлен символами ".". Например, если в начальный момент на ленте находились символы
.1 1 1 .
то в конце лента будет иметь вид
.111.
Пример 6 ( multiplication.java , multiplication.js ). Умножение двух чисел, заданных в унарной системе счисления. Пример взят без изменения с http://www.ams.org/new-in-math/cover/turing_multiply_code.html
В приложении turingmachine2.zip помещены все исходные тексты, результаты исполнения исходных программ. В директории Res_Multiplication - исполнение остаточной программы для последнего примера.