Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
II эт ап. Очевидно, мы имеем следующие оператор-
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ 141
ные схемы для преобразовании А0, ..., Аі} ..., Ау.
Ф(в? / &>«,
А5- * ^й}*р(й’в”)^0юїі \йРр^В(в’)1 г{4 Ф(а*~~і\в)Ри ,
А ^ уГкНщ й ї*Чф(а^^а)Яр}^С(е ^Шы,
А}~ * ^ Я** 1р(а 'а"){ та} и }* 7 Ф(в1 -~^а)Ррв^га’}І**1іо.
Лемма доказана.
Лемма 4 (о преобразовании квазиосновного кода в основной). Для любого натурального числа І [I** 2) можно построить машину Тъюринга, которая произволъ-ный квазиосновлой код ЬіиіЬ2...и^-іЬч, где \Ui\-... ..,*=* ИД-Д =1—1, преобразует в соответствующий основ-ной код 6^2. - - Ьч.
Доказательство. Ї этап. Искомая машина сначала отступает на некоторый промежуток вправо от ква-виосновного кода и затем постепенно там формирует основной код путем «перетаскивания» основного кода с решетки.
Более точно преобразование состоит в следующем.
1) В начальный момент обозревается символ Ьь т. е. символ в узле решетки с шагом I, на которой расположен основной код. Движемся по решетке на правый конец основного кода (оператор Л), осуществляя стирание буферных слов ии ич-1, лежащих вне решетки (См.
следствие 2 леммы 1).
2) Справа от правого конца (символ Ь?) вписываем З/ —1 нулей*) и одну единицу (оператор Ф (
>-6у0 ... О I1)), после чего попадаем на ту же решетку.
^ Я1-Г
3) Отыскиваем левый конец основного кода (оператор Г).
*) В квазиосновном коде может подряд стоять 21 — і нулей.
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
4) Пусть а'а"а"' — первые три символа в основном коде (в начальный момент это іцЬг&з). Вычисляем предикат р{а'а"й'"), принимающий три значения. При а" = і (основной режим) переходим к выполнению следующего за р оператора. При а" = 0, а"~ 1 а является последней
т J «
единицей в массиве п так как а = 1, то имеется по крайней мере еще одип массив — переходим к выполнению оператора, указываемого стрелкой с пометкой а" =0,
fff 4 п—г // /// j tj г*
а =1. При а =а =0 а является последней единицеп основного кода (т. е. а = bv) — переходим к выполнению оператора, указываемого стрелкой с пометкой а” *=
/ff п
“ а = и.
Основной режим а" =1.
5) Стираем символ а' (оператор 0(а')).
6) Движемся на правый копец основного кода (оператор Д).
7) Перемещаемся вправо еще на Зі ячеек (оператор Rf).
8) Выходим на правый конец формируемого кода (оператор R).
0) Приписываем справа единицу (оператор Ф(а*-> ->а1Д).
10) Движемся на левый конец формируемого кода (оператор L) и переходим к 3).
Режим а" =0, а " = 1.
Выполняем то же, что и в предыдущем режиме 5) —
10), кроме пункта 9), где выполняем оператор Ф(й^сОП-).
Режим а" = а" = 0.
Здесь стираем символ а' (оператор 0(а')) и, смещаясь вправо на 3Z ячеек (оператор R\s), попадаем на левый конец искомого основного кода и останавливаемся. II этан. Мы имеем следующую операторную схему;
*R<P(bl—bvB.;.0jh
_________Ш-1
Г
4»fo(?’a”s'"} ^ойпЩ1вФ(а^^а1Sip0j0(a)Щ1ЙФ(gи01 Slp? 0(Ь’)Р**о ' . a”-a m=0
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
143
? § 4. Вычислимые функции
Выше мы ввели систему содержащую все кон-
станты из Ек и все функции, определенные на наборах чисел из расширенного натурального ряда и ПрИШЬ мающие значения на ? . Сейчас мы определим более широкую, чем систему функций.
Пусть }(хи ..., зп) — функция, определенная на подмножестве Е} множества всех наборов (а,, ..ап) чисел
из..расшщ1?нного_ натурального ряда ЕНй и принимающая значения также из (вне множества Еу функция считается неопределенной). Такого рода функции будем называть частичными функциями счетнозначной логики.
Обозначим через Р* ~ множество веех частичных функций счетпозначной логики.
Как и в случае не всюду определенных функций из Р2 (см. гл. 3), можно ввести понятие несущественной переменной.
Определение. Переменная х,- называется несущественной для функции $(хи ..., ИЗ РЧц0, если существует функция /' из Р«0 такая, что
/'(*!, *») = /(«!, на Е} и переменная хх не существенна для 1'(хи хп).
В дальнейшем частичные функции будем рассматривать с точностью до несущественных переменных, относительно которых множество Е1 цилиндрично. В этом случае существует доопределение функции /, т. е. функция из Як0> которая несущественно зависит от всех таких переменных.
Определение. Функция /(#!, хп], где/еР^^ называется вычислимой, если существует машина Тьюринга такая, что:
а) при (а!, ..., ап)^Е1 машина 9Я, будучи применена к основному коду для (а{, а„) и находясь в началь-
ном состоянии над его левой единицей, останавливается -и в заключительном состоянии на ленте выдает код для/(<%!, ..., ап);
б) при (аи ..ап)&Е} машина 2ГС, будучи применена к основному коду для (оц, ,.а„) и находясь в начальном состоянии над его левой единицей, либо не останав-
гм 1. л. ипциии АЛЬНЬЩ СИСТЕМЫ С ОПЕРАЦИЯМИ
ливается, либо останавливается, но при этом запись на
ленте отлична от кода любого числа из ?, .
*0
Замечание. Константы из Еи можно также счи-
тать вычислимыми функциями с пустым множеством переменных в следующем смысле.
Пусть Рассмотрим машину, задаваемую
табл. 15. Покольку 7 — константа, то в начальном положении лента считается пустой. Очевидно, машина, начи-Т в б л л и а 15 Таблица 16
