Cтраница 1
Засылка констант в адресуемые регистры может выполняться в режимах как ручного, так и автоматического счета. Ручная засылка, когда на клавиатуре набирается число и выполняется команда ПМ ( где М - обозначение адресуемого регистра), не удлиняет программы. Однако, если имеются резервы командной памяти, лучше организовать автоматический ввод констант с помощью безликих команд СП, ПП или циклом. [1]
При засылке констант, разрядность которых кратна 8, следующий регистр необходимо пропустить. [2]
Подготовительная часть программы содержит формирование необходимых шагов индексирования и засылку констант индексирования в индексные ячейки, установку счетчиков. Шаг индексирования N; 1, получаемый операторами строк 070 - М 10, необходим для переадресации индексной ячейки при вычислении каждого элемента матрицы произведения. При этом запоминается величина 0; N, которая используется для формирования константы индексирования во внешнем цикле. Поскольку порядок матриц одинаков и все циклы выполняются N раз, подготавливается константа N-1 для счетчика. Это соответствует блоку 1 на блок-схеме. [3]
Пусть 5 - стандартная схема с одной переменной, в которой имеется k инструкций засылок констант, и пусть / - произвольная интерпретация. [4]
Мы покажем, что для любых данных стандартных схем R и 5 с одной переменной и засылками констант имеется эффективная граница, такая, что если R Ф S, то существует интерпретация, при которой R и 5 различаются и при этом длина истории вычислений одной из схем меньше, чем граница. Как и раньше, этого достаточно для доказательства теоремы, поскольку эквивалентность R и 5 в этом случае можно проверить выполнением схем при конечном числе конечных интерпретаций. [5]
Существует эффективная процедура для распознавания, являются ли сильно эквивалентными две стандартные схемы с одной переменной и засылками констант. [6]
Предположим, что R и 5 - схемы с не более чем е инструкциями, среди которых не более k засылок констант. [7]
Установив, что для некоторого подкласса класса рекурсивных схем проблема эквивалентности разрешима, мы покажем то же самое для класса стандартных схем с одной переменной и засылками констант. Проблема эквивалентности для стандартных схем с одной переменной без засылок констант разрешима, как было показано в разд. Следовательно, следующая теорема является оптимальной. [8]
Установив, что для некоторого подкласса класса рекурсивных схем проблема эквивалентности разрешима, мы покажем то же самое для класса стандартных схем с одной переменной и засылками констант. Проблема эквивалентности для стандартных схем с одной переменной без засылок констант разрешима, как было показано в разд. Следовательно, следующая теорема является оптимальной. [9]
Насколько мощным должен быть класс схем для того, чтобы проблема сильной эквивалентности схем данного класса была алгоритмически неразрешима. В этом разделе мы собираемся ответить на вопросы, поставленные де Беккером и Скоттом. Именно, мы покажем, что проблема эквивалентности для класса линейных рекурсивных схем разрешима. Далее, мы исследуем, насколько широкие расширения класса стандартных схем с одной переменной обладают разрешимой проблемой эквивалентности. В частности, мы покажем, что добавление к таким схемам засылок констант не влияет на разрешимость проблемы эквивалентности. [10]