Класс - стандартная схема
Cтраница 1
Класс стандартных схем над разобщенной памятью интересен в связи с открытой проблемой о разрешимости функциональной эквивалентности в этом классе. Для схем с двумя переменными данная проблема решается положительно. [1]
 |
Схема Патерсона всегда останавливается. [2] |
В классе стандартных схем особую роль играют схемы Янова. [3]
Обозначим через ( R класс стандартных схем программ. [4]
Класс схем dBS слабо транслируем в класс стандартных схем с одной ячейкой. [5]
Обозначим через Р ( переход) класс стандартных схем программ, в которых операторы перехода запрещены. Учитывая вышесказанное, справедлив следующий результат. [6]
Так как рекурсивные преобразователи над памятью являются расширением класса стандартных схем, то все проблемы ( типа функциональной эквивалентности), неразрешимые для стандартных схем, неразрешимы и для рекурсивных преобразователей. С другой стороны, разрешимые случаи в классе стандартных схем могут оказаться неразрешимыми или неизвестными для рекурсивных преобразователей. Интересным примером является проблема функциональной эквивалентности для схем с одной переменной. С одной стороны, хорошо известно, что для схем Янова она разрешима ( см. следствие 7.9), но для унарных рекурсивных схем ( схем Де Баккера и Скотт) - это известная открытая проблема. Доказано, что эта проблема равносильна проблеме эквивалентности в классе детерминированных КС-языков. Отсюда, в частности, следует, что проблема эквивалентности в классе LA ( 1) - систем равносильна проблеме эквивалентности для недетерминированных языков. [7]
 |
Схема Патерсона всегда останавливается. [8] |
Патерсон и А. А. Лети-чевский, проблемы остановки, расходимости и эквивалентности в классе стандартных схем программ алгоритмически не разрешимы. [9]
Из теоремы 3.4 следует, что некоторые естественные классы рекурсивных схем транслируемы в класс стандартных схем. [10]
Заметим, что слабые трансляции предыдущей теоремы можно превратить в сильные трансляции, если расширить класс стандартных схем, добавляя предикат Р и функцию / с фиксированной хорошей интерпретацией. Если же разрешить использование в стандартных схемах конечного числа счетчиков, то можно обойтись и без таких Р и /: поскольку машина с регистрами R представляет собой стандартную схему с конечным числом счетчиков, счетчики можно использовать для моделирования схемы R непосредственно в терминах приведенных выше конструкций. [11]
Установив, что для некоторого подкласса класса рекурсивных схем проблема эквивалентности разрешима, мы покажем то же самое для класса стандартных схем с одной переменной и засылками констант. Проблема эквивалентности для стандартных схем с одной переменной без засылок констант разрешима, как было показано в разд. Следовательно, следующая теорема является оптимальной. [12]
ЕСЛИ р ( х) ТО / ( л:) ИНАЧЕ gFFh ( x) не вычислима в классе стандартных схем программ. [13]
Так как рекурсивные преобразователи над памятью являются расширением класса стандартных схем, то все проблемы ( типа функциональной эквивалентности), неразрешимые для стандартных схем, неразрешимы и для рекурсивных преобразователей. С другой стороны, разрешимые случаи в классе стандартных схем могут оказаться неразрешимыми или неизвестными для рекурсивных преобразователей. Интересным примером является проблема функциональной эквивалентности для схем с одной переменной. С одной стороны, хорошо известно, что для схем Янова она разрешима ( см. следствие 7.9), но для унарных рекурсивных схем ( схем Де Баккера и Скотт) - это известная открытая проблема. Доказано, что эта проблема равносильна проблеме эквивалентности в классе детерминированных КС-языков. Отсюда, в частности, следует, что проблема эквивалентности в классе LA ( 1) - систем равносильна проблеме эквивалентности для недетерминированных языков. [14]
Обозначим через РВ класс схем программ над стандартной памятью, допускающих возвраты вышеописанного вида. Класс Р ( п, т) - класс стандартных схем с я-стеками ( по данным), способными запоминать промежуточные значения переменных, и т-маркерами, Рвм - класс схем, допускающих возвраты и обладающих дополнительной возможностью расставлять метки на значениях переменных, РА / П / - класс схем, допускающих индексирование переменных, маркеры в качестве значений переменных и предикат равенства. С точки зрения дискретных преобразователей класс РВМ является классом отмечающих преобразователей над стандартной памятью. Эти соотношения будут использованы в следующей теореме. [15]
Страницы: 1 2