art24.htm

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

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

2. Язык преобразования документов XSLT: эксперименты с суперкомпилятором Scp4.

2.4. Интерпретатор машины Тьюринга на языке XSLT.

      Интерпретатор VT.ref определяет семантику рассматриваего фрагмента языка XSLT в терминах Рефала. Второй интерпретатор, рассматриваемый в этом параграфе, является интерпретатором машины Тьюринга, и написан он на языке XSLT.

      Предъявление такого интерпретатора машины Тьюринга является доказательством алгоритмической полноты данного подмножества XSLT.

      Для проведения сравнительных экспериментов были подготовлены следующие документы :

TM.dtd - описание области определения программ TM.xsl , TMPQ.xsl и TMDoublePQ.xsl,

TM.xml - входные данные для программ TM.xsl , TMPQ.xsl и TMDoublePQ.xsl,

TM.xsl - интерпретатор машины Тьюринга , обработка краев ленты не предусмотрена, эксперименты производились для конкретной машины Тьюринга из примера DoublePQ,

TMPQ.xsl - вариант предыдущей программы, работающей с конкретной машиной Тьюринга - замены символов P на Q,

TMDoublePQ.xsl - вариант предыдущей программы, работающей с конкретной машиной Тьюринга - удвоение букв P с заменой их на Q.

TMN.dtd - описание области определения TMNPQ.xsl и TMNDoublePQ.xsl,

TMN.xml - входные данные для программ TMNPQ.xsl и TMNDoublePQ.xsl,

TMNPQ.xsl , TMNDoublePQ.xsl - варианты TMPQ.xsl,TMDoublePQ.xsl , в которых предусмотрена обработка краев ленты, при необходимости справа или слева добавляются пустые клетки.