Cтраница 1
Счетчиковый автомат состоит из конечного множества счетчиков х - 11 / л, алфавита и программы автомата. [1]
Счетчиковый автомат порождает ( печатает) слово в алфавите автомата, продвигаясь по программе, меняя значения счетчиков и печатая очередной символ. Движение начинается в начальной вершине. Оператор недетерминированного перехода выбирает произвольным образом направление дальнейшего движения. [2]
Счетчиковый автомат на рис. 5.2 реализует декодирующую функцию К-1, которая является частично-рекурсивной. Этот автомат имеет два счетчика х и у, он останавливается и печатает слово К 1 ( т), если т является начальным значением счетчика х и одновременно числом-кодом. В противном случае автомат зацикливается. [3]
Для построения ингибиторной сети, моделирующей счетчиковый автомат, достаточно каждому оператору программы автомата сопоставить моделирующий его фрагмент ингибиторной сети и затем связать эти фрагменты в единую сеть. Переходы, соответствующие операторам печати, помечаются соответствующими символами, остальные переходы вводятся как Л - переходы. Фрагменты связываются в сеть путем слияния одинаково помеченных выходных и входных мест. [4]
Способ, которым строится помеченная ин-гибиторная сеть, моделирующая счетчиковый автомат, непосредственно убеждает в эквивалентности терминальных языков, порождаемых обеими системами, если для сети фиксировать терминальный язык с такой резмет-кой Mf, при которой все места сети, кроме места, соответствующего оператору стоп, имеют нулевую разметку, а это место - единичную. Таким образом, класс Со ( /) всех терминальных языков ( помеченных) ингиби-торных сетей является классом рекурсивно перечислимых языков. Класс СЛ ( /) образован префиксами языков из класса JCo ( /) рекурсивно перечислимых языков и поэтому он также является классом рекурсивно перечислимых языков. [5]
Теорема 5.1. Любой рекурсивно перечислимый язык может быть порожден некоторым счетчиковым автоматом. [6]
Достаточно продемонстрировать, как в иерархических сетях можно промоделировать оператор условного вычитания единицы счетчикового автомата. [7]
Таким образом, любой рекурсивно перечислимый язык является образом некоторого рекурсивно перечислимого множества чисел при декодирующей функции К-1, вычисляемой некоторым счетчиковым автоматом. В свою очередь, каждое рекурсивно перечислимое множество чисел является областью значений некоторой частично-рекурсивной функции f, которая может быть задана машиной Минского. [8]
Чтобы убедиться в этом, достаточно показать неразрешимость более узкой проблемы, а именно - не существует алгоритма, который для любого счетчика может установить, будет ли его начальное нулевое значение изменено хотя бы один раз, т.е. является ли счетчик 0-ограниченным или нет. Введем дополнительный вспомогательный счетчик х, запись в который делается только после того, как исходный автомат останавливается, выполнив заключительный оператор стоп. Для этого достаточно заменить этот оператор на последовательность операторов ж: х 1 и стоп. Если бы была разрешима проблема 0-ограниченности, то мы могли бы решать проблему остановки счетчикового автомата, воспользовавшись описанным преобразованием. Таким образом, проблема Оюграниченность не может быть разрешимой и, следовательно, неразрешима более общая проблема ограниченности счетчиков и проблема ограниченности ингибиторной сети. [9]