Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
«1 ’‘т «1 и*
0 1 Ву.2 1 /?х3 ... 1?ку+г 0
1 1 0ЙН1
ная от исходной ячейки, движется вправо и формирует массив из ч + 1 единиц — код и затем возвращается на левый конец массива.
Приведем пример вычислимой функции.
Пример 6. Покажем, что функция 0(х)^0 вычислима. Для этого возьмем машину, определяемую табл. 16. Очевидно, что эта машина «реализует» функцию Заметим, что данная машина «реализует» также функцию Цх\, = 1 и константу 0 (как функцию, зави-
сящую от пустого множества переменных).
Обозначим через Рьыч класс всех вычислимых функций. Очевидно, РцЫЧ^РЧхь.
Определение. Машина Тьюринга 2Я реализует (вычисляет) функцию /(#!, хп) (из класса Рвыч) правильным образом, если:
а) при (й1, ..., аи)е Е) машина 5Ш, будучи применена
к основному коду для (<*!, ..., а„) и находясь в началь-
ном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для /(<Хц а„)\ при этом останов происходит над левой
единицей кода для /(<*), .... а„);
б) при {аи ап)*?Е} машина 20?, будучи применена
к основному коду для (аи ..., а„) и находясь в началь-
ном состоянии над его левой единицей, не останавливается.
Легко видеть, что машина (см. табл. 16) реализует О (х).ш 0 правильным образом. -
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
145
Лемма 5. Если /(.г3, ..., ггп)—вычислимая функция, то существует машина Тьюринга, которая вычисляет ее правильным образом.
Доказательство. Пусть 2Я' — машина, вычисляющая функцию $(хи ...» хп). Соответствующее преобразование записи ленты, положения головки и состояний обозначим через А'. Рассмотрим преобразование
А = *КхА'р ОД3со.
Здесь Ку — преобразование кода для (сс1( ..ап) в удвоенный код с буферным словом 01. На первой решетке будет код для (аь а„), на второй — сплошной массив из единиц.
Л' — преобразование, моделирующее на первой решетке преобразование А'; вне этой решетки Л' в рабочей зоне ставит символ 1.
р — предикат, выясняющий вид слова на первой решетке после работы оператора Л'. Просмотр слова осуществляется при помощи второй решетки, которая своим массивом из единиц отмечает зону обследования на первой решетке. Полагаем р = 1, если слово является массивом из единиц, и р ~ 0, если в слове найдутся две единицы, между которыми имеется нуль, или в нем нет единиц вообще.
02 — преобразование, которое стирает все единицы на второй решетке и останавливается над левой единицей слова, расположенного на первой решетке.
К3 — преобразование квазиосновного кода в основной.
Из данной схемы видно, что в случае, когда после осуществления преобразования Л' запись на первой решетке будет отлична от массива из единиц, преобразование зацикливается, так как будет все время вычисляться предикат р.
Машина ЭЯ, соответствующая преобразованию А, и будет искомой.
Лемма доказана.
В дальнейшем для вычислимых функций будем использовать исключительно машины, вычисляющие их правильным образом.
Теперь перейдем к описанию некоторых простейших вычислимых функций. Рассмотрим следующие функции:
Ю С. В. Яблонский
Таблица 17а
8 к» к,
0 1 1Ухв 1 Ькг
145 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
1) константа 0; 2) ?(х) = х + 1; 3) (г±, .. хп) = хтт
где 1 < тп < п.
Покажем, что данные функции вычислимы. Это уже сделано для константы 0. Вычислимость функций 5(л’) и 1т следует из того, что они реализуемы следующими машинами (см. табл. 17а, б). Машина для Гт{хХу а,,) идет направо (в начальном состоянии обозревается, как
Таблица 176
1п ТП «I ит—I у-т
0 І 0 Ли, 0/?х1 0Лхт 0Лхт_н 1 Лхт
1п 1 хп «П-Н1 х«+2 кп4-з
0 1 2 0Дкй 0'1ма+1 1 ? хп_; 2 0Лив+в
всегда, левая единица основного кода) п стирает все массивы основного кода для (а,, .... ап), кроме т-го, затем возвращается влево и встает над левой единицей оставшегося массива.
§ 5. Операцпп С, Пр и ц
На множестве определим три операции: С (су-
перпозиция), Пр (примитивная рекурсия) и ц (минимизация) ,
Операция суперпозиции вводится так же, как и для предыдущих функциональных систем: сначала определяется понятие формулы %{хи #„) над данной системой функций из^к0, потом каждой формуле 31 сопоставляется функция}%(хи .. .4 хп), принадлежащая^«^ При этом,
если иа наборе (а,, ..а„) окажется, что одна из функций, входящая в будет неопределенной, то считаем, что /а(аи " ч ак)будет также неопределенной. Более точно, пусть
Ф X7,) ' * / {/1 {•? 1} • • *»? Хл) ] ? * /та (^Ч) * * »1 Хп) ) ,
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ 147
Возьмем произвольный набор {аи .ак) чисел из расширенного натурального ряда. Если на этом наборе определены функции /і, ..., и функция / определена па наборе (/і(сса, ссп), ..., сі„)), то Ф определена на (ал, ап) и Ф(аи ..а«) — / (А («і, ..., а„), ...
..{т(аи ..ап)); в противном случае Ф не определена на наборе (аи ..к„).
Операция примитивной рекурсии определяется следующим образом.
Пусть ф(жй хп) и г[з(а:11 ..хп, жп+1, л:п+2)*)’ — произвольные функции ИЗ Р ^ . Построим функцию /(#!, ... хп, используя «схему» примитивпой рекурсии:
і(сси ..хп, 0) = ф (ж,, ..ж;)',
/(ж4, ..жП1 у + 1)= жп, у, /{Жі, ..., хп, у)).
