Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
В частности, может оказаться необходимым сохранить исходное задание. В таком случае его можно скопировать в какой-либо части ленты (например, с помощью машины, выполняющей транскрибирование) и сохранять его там с помощью некоторой машины Z1 указанного в предыдущем абзаце типа.
5.1.2. Упражнение. Машина с маркерами
Пусть имеется стандартная машина Z с алфавитом
[Sq (или В), S1 (или I), S2, ...} Гл. V. Вычислимость и разрешимость
83
и состояниями <7ь Цг, ..., Требуется построить машину Z', которая выполняла бы те же вычисления, что и Z, но обрамляла бы результат маркерами у слева и б справа (если какой-нибудь из этих символов уже есть в алфавите машины Z, то его, разумеется, необходимо заменить).
Указания:
а) Построить машину Z1, которая читает исходное задание, находит его концы по наличию двух пустых ячеек подряд, ставит маркеры у и б, а затем перемещает ленту так, чтобы головка обозревала у-
Чтобы определить Z1, достаточно пяти состояний.
б) Построить машину Z2, добавив к состояниям машины Z1 пять новых состояний, а к ее программе такие команды, в соответствии с которыми Z2 будет в случае необходимости перемещать у (или б) на одну ячейку влево (соответственно вправо) и возвращаться всякий раз к основному вычислению.
в) Построить стандартную машину Z3, соответствующую машине Z2.
г) Построить машину Zi, которая стирала бы на ленте все символы, кроме палочек, собирала бы все палочки вместе и добавляла к ним еще одну (чтобы результат можно было понимать как число).
5.1.3. Упражнение
а) Построить машину Тьюринга, которая кодировала бы алфавит {а, Ь, с} с помощью алфавита {0,_ 1} по образцу, описанному в предыдущей главе.
б) Построить машину, которая расшифровывала бы указанную кодировку, а для нерегулярных слов (не являющихся кодами) распознавала бы их нерегулярность.
§ 5.2. ОПЕРАЦИИ НАД ФУНКЦИЯМИ
Вернемся теперь к функциям, отображающим Nn в N.
5.2.1. Композиция
Пусть имеется, с одной стороны, функция от m переменных
f (х 1, . . ., Xm),
определенная на Dc Nm, с другой стороны, m функций от п переменных
gi(yi, • ••> Уп),
ёт(У\, ¦¦¦> Уп), где каждая gi имеет область определения Di с= Nn. 84
Часть /. Предварительные сведения из логики и алгебры
Операция композиции сопоставляет этим функциям новую функцию
h (г/i.....yn) = f[gi ІУі, Уп).....Sm (У і > • ••> Уп)Ь
Областью определения функции h является подмножество пересечения Dif) ... Г)An, состоящее из всех n-ок, для которых значения функций gl, ..., gm дают точку из D.
Основным результатом, относящимся к композиции вычислимых функций, является следующая
Теорема. Если функции /, ^1, ..., Sm частично вычислимы (соответственно вычислимы), то функция h также частично вычислима (соответственно вычислима).
Доказательство этого предложения проводится с помощью композиции стандартных машин Тьюринга, соответствующих функциям f, gi, ..., gm- Само по себе доказательство не сложно, и мы предоставляем его читателю в качестве упражнения.
Из данной теоремы непосредственно следует, что классы вычислимых я частично вычислимых функций замкнуты относительно композиции.
5.2.2. Минимизация
Операция минимизации сопоставляет функции f(y, хи ..., хп), определенной всюду на Nn+i, функцию h(xi, ..., хп), значение которой для любой данной n-ки равно наименьшему значению у, такому, что f(y, xi.....хп) — 0, если только такие значения у существуют; если же для данных xi, ..., хп функция xi, . ¦ . , xn ) не обращается в нуль ни при каких значениях у, то Ii(xi, ..., хп) для данных xi, ..., xn не определена.
Функция h, таким образом, может оказаться определенной лишь на некотором подмножестве множества JV"; если h определена на всем множестве Nn, то функция f(y,
xi, . . . , xn ), из которой h получается минимизацией, называется регулярной.
Основным результатом, относящимся к минимизации, является следующая
Теорема. Если функция f (у,
xi, . . • , xn ) вычислима, то функция h, полученная из нее минимизацией, частично вычислима. Если при этом функция f регулярна, то функция h вычислима.
Эта теорема доказывается путем построения машины Тьюринга, которая вычисляет последовательного, хи ..., хп), /(1, Jcb ..., хп),... до тех пор, пока для f не будет получено значение нуль (если функция f никогда не обращается в нуль, машина будет продолжать вычисления вечно). Здесь опять следует использовать стандартные машины Тьюринга. Гл. V. Вычислимость и разрешимость
85
5.2.3. Упражнения
1. Доказать теорему о композиции функций.
2. Минимизация:
а) Построить стандартную машину Тьюринга Т, которая каждой п-ке (хи ¦ ¦¦, хп) сопоставляла бы (и+ 1)-ку (О,х\, ..., хп).
б) Пусть f(y,xі, ..., хп) — (частично) вычислимая функция. Доказать, что существует стандартная машина U, которая сопоставляет любым заданным п + 1 числам у,хи хп представление системы чисел \}(у, X1, ..., Xn), у, Х\, ..., хп], если только f(y,xu ..., хп) существует.
Увеличить индексы состояний машины U так, чтобы ее можно было присоединить к Т.
