Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 27

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 21 22 23 24 25 26 < 27 > 28 29 30 31 32 33 .. 101 >> Следующая


Исходя из машины 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. Построить машину Тьюринга, которая писала бы зеркальный образ заданного слова.
Предыдущая << 1 .. 21 22 23 24 25 26 < 27 > 28 29 30 31 32 33 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed