Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Исходя из машины Z, мы пришли к функции с целыми неотрицательными значениями, определенной на множестве Nn или, быть может, на некотором подмножестве множества Nn (частично определенная функция) 4).
Поступим теперь наоборот: попробуем исходить из функций, определенных на Nn или его подмножестве.
Определение. Будем говорить, что функция f, определенная на некотором подмножестве множества N , является частично вычислимой, если существует машина Тьюринга Z, такая, что для всякой п-ки (лгь ..., хп), которой отвечает некоторое значение /, выполняется равенство
____fix......*„) = (X1,..., Xn).
!) Здесь и далее N означает натуральный ряд (включающий нуль), a Nn-множество всевозможных упорядоченных я-ок натуральных чисел. — Прим. ред. 78
Часть /. Предварительные сведения из логики и алгебры
Назовем функцию / вычислимой, если она определена на Nn и является частично вычислимой').
4.3.2. Пример вычислимой функции
Функция f(x, у) = X + у, определенная на множестве пар неотрицательных целых чисел, является «вычислимой в интуитивном смысле»; покажем, что она вычислима и в смысле Тьюринга. Для этого построим машину Тьюринга Z с алфавитом {В, |}, такую, что
X+у = Wi?(X, у).
Такая машина должна, имея на ленте коды х и у, разделенные пустой ячейкой, получать из этой записи х + у палочек (не обязательно подряд). Заметим, что
х + у = (х} + (9)-2.
Читатель без труда убедится, что следующая машина выполняет поставленную задачу:
qx I В q2 (1) Стирается первая палочка первого кода.
q2 В Л q3 (2) ] Лента сдвигается до тех пор, пока
q3\ Л q3 (3) У головка не дойдет до первой палочки
q3 В Л qA (4) J второго кода.
qi I В q4 (5) Стирается первая палочка второго кода.
Здесь машина останавливается, поскольку ситуации q? нет ни в одной команде. В этот момент на ленте ровно х + у палочек.
4.3.3. Пример частично вычислимой функции
Функция g(x,y) = x — у определена лишь для тех пар, у которых покажем, что она частично вычислима в смысле Тьюринга.
Для этого мы построим машину Тьюринга Z, выполняющую вычитание. Пусть на ленте имеются коды хну, разделенные пустой ячейкой: X слева, у справа. Машина будет работать последовательными циклами; каждый цикл состоит в стирании одной (самой левой) палочки в х и одной (самой правой) палочки в у. Вот соответствующая программа.
I В </[ (1) Стирается самая левая палочка в х.
<7, В Л q2 (2) Лента сдвигается на одну ячейку влево.
') Более принята другая терминология: частичную функцию f(xі, ..., хп) называют вычислимой, если существует машина Тьюринга Z, такая, что для всякой я-ки xit ..., хп, которой отвечает значение /, выполняется равенство
/(*,.....^) = ^(^. *„).
а для тех п-ок, для которых значения / не существуют, машина работает вечно. — Прим. ред. Гл. IV. Алгоритмы. Машины Тьюринга
79
q2\ Л q2 (3) Лента сдвигается влево до тех пор, пока головка не дойдет до конца кода х.
q2 В Л q3 (4) Головка переходит через пробел (пустую ячейку), разделяющий х и у.
q3 I Л q3 (5) Лента сдвигается влево до тех пор, пока головка не дойдет до конца кода у.
q3 В П <74 (6) Попав на пустую ячейку, примыкающую к у справа, головка возвращается на одну ячейку назад (т. е. к самой правой палочке у).
<74 I В <74 (7) Самая правая палочка в у стирается.
<74 В П <75 (8) Лента сдвигается на одну ячейку вправо и машина переходит в «проверочное» состояние.
Дело в том, что продолжение или прекращение вычисления зависит от результатов некоторых проверок.
<75 I Я <76 (9) Если обозреваемая ячейка содержит палочку (у еще не стерт полностью), вычисление продолжается. Если же обозреваемая ячейка пуста, то, поскольку ситуации qbB не отвечает никакая команда, машина останавливается.
<76 I Я <76 (10) Лента сдвигается вправо до тех пор, пока головка не дойдет до начала кода у.
<76 В Я q7 (11) Головка переходит через пробел, разделяющий у их.
q7 I Я <7з . (12) Если в х осталась хотя бы одна палочка, вычисление продолжается.
<7? В Я <77 (13) Если в к не осталось ни одной палочки (случай х<у), машина будет работать вечно, сдвигая ленту вправо.
<78 I Я <78 (14) Лента сдвигается вправо до тех пор, пока головка не дойдет до начала того, что осталось от кода X.
<78 В Л <7i (15) Головка устанавливается так, что обозревается самая левая палочка «остатка» кода х; машина переходит в начальное состояние <?,. Тем самым она оказывается готовой начать очередной цикл.
Частично вычислимую функцию х — у нетрудно тривиальным образом продолжить до вычислимой функции (это делается ниже, в упр. 4.4.8). Из этого, разумеется, нельзя делать вывод, что всякую частично вычислимую функцию можно продолжить до вычислимой.
§ 4.4. УПРАЖНЕНИЯ
1. Построить машину Тьюринга, которая копировала бы заданное слово, оставляя между соседними буквами пустые ячейки (т. е. переписывала бы его «вразрядку»). 80
Часть /. Предварительные сведения из логики и алгебры
2. Построить машину Тьюринга, которая окаймляла бы маркерами заданное слово.
3. Построить машину Тьюринга, которая писала бы зеркальный образ заданного слова.
