turing

turing.htm

Суперкомпиляция двойной интерпретации

(как один час машинного времени можно превратить в одну секунду)

1. Машина Тьюpинга

В теоpии алгоpитмов в качестве точного математического эквивалента для общего интуитивного пpедставления об алгоpитме используется понятие машины Тьюpинга . The American Mathematical Society has a page describing Turing machines [21].

Пpогpамма для машины Тьюpинга состоит из последовательности инстpукций. Каждая инстpукция имеет вид

CurrentState   CurrentSymbol   NextSymbol   NextState   Movement

Пpедполагается, что в обе стоpоны от введенной последовательности символов находится бесконечное количество символов пpобел (пробел будем обозначать символом B).

Hачальное внутpеннее состояние - 'start', конечное внутреннее состояние - 'stop'.

Рассмотрим пример программы для машины Тьюринга, который будет многократно использоваться в дальнейшем - пример DoublePQ удвоения количества символов P на ленте с заменой их на символы Q. Если, к примеру, на ленте в начале работы находится 10 (подряд написанных) букв P, и головка указывает на первую из них, то в конце будут находиться 20 букв Q.

( 3 ) CurrentState CurrentSymbol NextSymbol NextState Movement start B B stop right start Q Q start right start P Q moveleft left moveleft Q Q moveleft left moveleft B Q start right

В качестве предварительного эксперимента мы рассмотрим суперкомпиляцию интерпретатора машины Тьюринга, который написан на Рефале.

Интерпретатор выглядит так

*$MST_FROM_ENTRY; ( 4 ) * Call for a concrete Turing machine ( the program ). $ENTRY Go { (e.tapeleft) (s.CurrentSymbol) (e.taperight) = <Turing ( (start B B stop right) (start Q Q start right) (start P Q moveleft left ) (moveleft Q Q moveleft left ) (moveleft B Q start right) ) (start) (e.tapeleft) (s.CurrentSymbol) (e.taperight) >; } * The interpreter itself. <Turing (e.Program) * (s.CurrentState) * (e.LeftPartOfTape) * (s.CurrentSymbol) * (e.RightPartOfTape)> Turing { (e.instr) (stop) (e.left) (s.symbol) (e.right) = (e.left) (s.symbol) (e.right) ; (e.instr) (s.q) (e.left) (s.symbol) (e.right) = <Turing (e.instr) <Turing1 <Search (s.q s.symbol) (e.instr)> (e.left) (s.symbol) (e.right)> >; } Turing1 { (s.c s.r left) ( ) (s.symbol) (e.right) = (s.r) ( ) ( B ) (s.c e.right) ; (s.c s.r left) (e.left s.a) (s.symbol) (e.right) = (s.r) (e.left) (s.a) (s.c e.right) ; (s.c s.r right) (e.left) (s.symbol) ( ) = (s.r) (e.left s.c) ( B ) ( ) ; (s.c s.r right) (e.left) (s.symbol) (s.a e.right) = (s.r) (e.left s.c) (s.a) (e.right) ; } Search { (s.q s.b) ((s.q s.b s.NextSymbol s.NextState s.Movement) e.instr) = (s.NextSymbol s.NextState s.Movement); (s.q s.b) ((e.1) e.2) = <Search (s.q s.b) (e.2)>; }

Входная точка Go зафиксировала специализацию интерпретатора по конкретной машине Тьюринга. После суперкомпиляции получаем программу

( 5 ) * InputFormat: <Go (e.TapeLeft)(s.CurrentSymbol) (e.TapeRight)> $ENTRY Go { (e.101) (s.103) (e.104) = <F6 (e.101) s.103 e.104>; } F59 { ( ) ( ) Q = ( Q Q Q B ) ( B ) ( ); ( ) (s.119 e.104 ) Q = <F6 ( Q Q Q ) s.119 e.104>; (e.101 s.118) (e.104) Q = <F59 (e.101) ( Q e.104) s.118>; (e.101) ( ) B = (e.101 Q Q B ) ( B ) ( ); (e.101) (s.123 e.104) B = <F6 (e.101 Q Q ) s.123 e.104>; } F6 { (e.101) B = (e.101 B ) ( B ) ( ); (e.101) B s.105 e.104 = (e.101 B ) (s.105) (e.104); (e.101) Q = (e.101 Q B ) ( B ) ( ); (e.101) Q s.109 e.104 = <F6 (e.101 Q ) s.109 e.104>; ( ) P = ( Q Q B ) ( B ) ( ); ( ) P s.117 e.104 = <F6 ( Q Q ) s.117 e.104>; (e.101 s.116 ) P e.104 = <F59 (e.101) (e.104) s.116>; }

Для получения коэффициентов ускорения выполнения мы подготовили пример из 512 единиц.

Суперкомпилятор SCP4 преобразует программы на диалекте Рефал-5 [3]. Выполнение рефал-программы состоит из последовательности элементарных действий, называемых шагами [3]. Время исполнения шага Рефал-машины, вообще говоря, не является равномерно-ограниченным по данным. Конкретное проявление этой неограниченности зависит от реализации Рефала. Кроме того, в статье используется только подмножество Рефала-5 ( strict Рефал ), в котором: в образцах не допускаются открытые e-переменные и повторные t- и е-переменные [3]; левая часть предложения состоит из одного образца. Везде далее мы будем иметь ввиду это подмножество Рефала и конкретную релизацию Рефала-5 [7]. В данных условиях, время исполнения шага машины , соответствующего некоторому Рефал-предложению, равномерно ограничено тогда, когда в этом предложении нет повторных t- и е-переменных в правой части. Обратное неверно. Время исполнения каждого шага программы (4) равномерно ограничено по данным, если же входной точкой объявить Turing, то шаги соответствующие второму предложению этой функции не обладают таким свойством.

До суперкомпиляции количество Рефал-шагов равняется 2 634 778, время исполнения - 15.242 секунды, после суперкомпиляции количество Рефал-шагов равняется 525 319, время - 2.053 секунды. Таким образом, мы имеем ускорение по шагам SpeedupSteps = 5.016, ускорение по времени SpeedupTime = 7.388.

Примеры выполнялись на компьютере с процессором intel Pentium-3,
частота 500MHz, оперативная память 256 МB, операционная система
Windows2000.

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

В дальнейшем мы будем рассматривать именно этот более простой случай, каждый раз упоминая, что же получается в общем случае.

Уберем в исходной Рефал-программе в функции Turing1 первое и третье предложения, тогда после суперкомпиляции получается следующая более обозримая программа :

( 6 ) * InputFormat: <Go (e.TapeLeft)(s.CurrentSymbol) (e.TapeRight)> $ENTRY Go { (e.101) (s.103) (e.104) = <F6 (e.101) s.103 e.104>; } F27 { (e.101 s.117) (e.104) Q = <F27 (e.101) (Q e.104) s.117>; (e.101) (s.121 e.104) B = <F6 (e.101 Q Q ) s.121 e.104>; } F6 { (e.101) B s.105 e.104 = (e.101 B ) (s.105) (e.104); (e.101) Q s.109 e.104 = <F6 (e.101 Q ) s.109 e.104>; (e.101 s.116) P e.104 = <F27 (e.101) (e.104) s.116>; }

Здесь все прекрасно видно. Функция F6 соответствует внутреннему состоянию start , функция F27 соответствует внутреннему состоянию moveleft. Каждое предложение соответствует одной инструкции программы для машины Тьюринга. Количество Рефал-шагов равняется количеству шагов машины Тьюринга. В результирующей программе отсутствуют термины start, moveleft, stop.

Выходом суперкомпилятора является оптимальная программа на Рефале, то есть произошла компиляция программы для машины Тьюринга (3) в Рефал-программу (6). Здесь под "оптимальностью " мы имеем ввиду оптимальность в рамках описанного нами ранее алгоритма: никакого изменения алгоритма "по существу " не произошло.