Линейная рекурсивная схема

Cтраница 1

Линейная рекурсивная схема Е примера 2.1 не является сильно эквивалентной никакой стандартной схеме с одной переменной, а также никакой праволинейной схеме, поскольку язык L ( E) нерегулярен. Стандартная схема S примера 2.2 не является сильно эквивалентной никакой рекурсивной схеме, поскольку L ( S) не является контекстно-свободным. [1]

Существует линейная рекурсивная схема, которая не является сильно эквивалентной никакой праволинейной рекурсивной схеме. [2]

Всякая линейная рекурсивная схема транслируема в сильно эквивалентную стандартную схему. [3]

Таким образом, функции, задаваемые линейными рекурсивными схемами, можно вычислять достаточно эффективно, используя лишь фиксированное число ячеек. Однако, по-видимому, для реализации этой возможности требуется более гибкая структура управления, чем та, которая имеется в стандартной схеме. [4]

Существует рекурсивная схема, которая не является сильно эквивалентной никакой линейной рекурсивной схеме. [5]

Существует эффективная процедура для распознавания, являются ли две линейные рекурсивные схемы сильно эквивалентными. [6]

В силу леммы 1.2 достаточно показать, что алгоритмически разрешима следующая проблема: для двух данных произвольных линейных рекурсивных схем R и S узнать, существует ли свободная интерпретация, которой они различаются. А для этого достаточно получить эффективную границу длины кратчайшего результата одной из схем для тех свободных интерпретаций, при которых другая схема либо зацикливается, либо дает другой результат. Если такая граница дана, то сильную эквивалентность схем R и S можно распознать, вычисляя значения обеих схем при конечном числе конечных интерпретаций, области dom / которых состоят из всех цепочек функциональных символов длины не большей, чем эта граница. [7]

Стандартная схема L, эквивалентная линейной рекурсивной схеме L. [8]

Заметим, однако, что в этом примере при любом вычислении непосредственно может потребоваться максимум одно новое значение определяемой функции. Это свойство и характеризует линейные рекурсивные схемы. [9]

В разделе 5 рассматривается приложение техники следов. Показано, что проблема эквивалентности разрешима в классе линейных рекурсивных схем ( что является частичным ответом на вопрос, поднятый де Беккером и Скоттом в [1]) и в классе схем Янова с постоянными функциями. [10]

С данной унарной схемой ассоциируются два сорта языков и формулируется несколько теорем о нетранслируемости, непосредственно вытекающих из классических теорем теории формальных языков. Кроме того, некоторые естественные классы рекурсивных схем ( например, линейные рекурсивные схемы) можно строго определить, задавая сопоставленные им языки. Точно так же некоторые результаты теории формальных языков наводят на мысль об аналогичных результатах для схем: например, теорема Хомского о нормальной форме для КС-языков приводит нас к факту, что всякая унарная рекурсивная схема эквивалентна такой рекурсивной схеме, в которой термы определяющих соотношений содержат не более двух определяемых функциональных символов. [11]

Насколько мощным должен быть класс схем для того, чтобы проблема сильной эквивалентности схем данного класса была алгоритмически неразрешима. В этом разделе мы собираемся ответить на вопросы, поставленные де Беккером и Скоттом. Именно, мы покажем, что проблема эквивалентности для класса линейных рекурсивных схем разрешима. Далее, мы исследуем, насколько широкие расширения класса стандартных схем с одной переменной обладают разрешимой проблемой эквивалентности. В частности, мы покажем, что добавление к таким схемам засылок констант не влияет на разрешимость проблемы эквивалентности. [12]

В разделе 3 приведены результаты, получаемые с помощью программистской техники; этот раздел содержит общие теоремы о транслируемости. Это определение не ставит ограничений на порядок, в котором проводятся вычисления, а требует только, чтобы результаты, если они определены, были одними и теми же. Показано, что квазирациональные рекурсивные схемы ( наименьший класс схем dBS, содержащий линейные рекурсивные схемы и замкнутый относительно функциональной подстановки) транслируемы в унарные стандартные схемы. Весь класс схем dBS также транслируем в класс стандартных схем, снабженных двумя счетчиками, - т результат, который для бинарных рекурсивных схем оказывается неверным. Программистская техника используется также для того, чтобы показать, что класс языков значений стандартных схем в точности совпадает с классом всех рекурсивно-перечислимых языков. Это не только разрешает все наши споры, но говорит также о том, что методы раздела 2 не имеют так много приложений, как можно было бы надеяться. [13]

Во-первых, существуют стандартные схемы Т с двумя счетчиками, для которых 1еп ( Г, п) не ограничено никакой рекурсивной функцией от / г, - факт, который следует из того, что не существует рекурсивной границы для длины вычисления универсальной машины с двумя регистрами. Во-вторых, как показано в разд. Приведенный пример 4.2 почти оптимален, так как всякая линейная рекурсивная схема сильно эквивалентна некоторой стандартной схеме. [14]

Страницы: 1