Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 38
Текст из файла (страница 38)
Например, функция определена лишь тогда, когда — —. 3 — у,72 целое неотрицательное число, 3 — — целое положительное число у 2 р и .- целое неотрицательное число. 3 — у7'2 Решение примера 4. Имеем 2я — 1 при я>1, не определено при х = О.
Нужно построить такун7 машину Тьюринга Т, которая «перера- батывает» любое слово 1 + (при ц > Ц в слово 1 " и удовлетворяет условию: либо Т(1) не определено, либо Т(Ц не является основным машинным кодом никакого числа из Ле. Попытаемся реализовать следующую идою: стирая самую леную единицу в слове 1«'4 (о > 0) и проходя оставшееся подслово 1 слева направо., головка пропускает еще одну (пустую) ячейку («раз- делительный нуль») и печатает две единицы подряд; получается слово 1 01; затем головка возвращается к левой единице подслова 1 (если такая единица есть), вычеркивает ее, проходит новое подсло- во 1" 7 слева направо, потом проходит «разделительный нуль» и две ранее напечатанные единицы (справа от него), печатает еще две еди- ницы и опять возвращается к началу «остатка» исходного слова 1 +~ и т.д., когда в исходном слове все единицы будут вычеркнуты, а во «вновь формируемом» массиве все единицы будут напечатаны, то на ленте «останется» массив из 2ее+ 2 единиц; вычеркнем в нем две первые единицы и «процесс вычисления» закончим.
Программа машины Тьюринга Т, реализующей описанную идею, выглядит так: Ч10Ч40Л Ч41Ч70Л Ч71ЧгОЛ ЧьОЧь04 ЧяОЧъОЛ Чь1Чь ц Чя1Чг1Л ЧьОЧгОЛ ЧЗОЧ41Л Че1Ч61л' Чг1Чз1Л Ч717!оОЛ Ч40Чь И Имеем Т(1 «7) = 17 при о > 1 и Т(1) = Л (пустос слово).
Значит, машина Т действительно вычисляет заданную функцию Д(я), но не является машиной Тьн>ринга, правильно вычисляющей эту функцинз (так как она, применима к слову 1, соответствующему значению я = О, а. на этом значении аргумента функция Дх) не определена). Чтобы из машины Т построить машину Т', правильно вычисляющую функцию 1(л), достаточно удалить из программы машины Т команду Ч71ЧоОЛ и добавить команды Ч71ЧьОЛ и Чь071ьОЯ. 1 д Машины Тьюринеа и операции над номи 193 1.14. Построить машину Тьюринга, вычисляющую функцию 1: ГО,. если х = О, 1) 7"1х) = я8х = ~ ' ' 2) 1'1х) = я8х = 1 — яях; 11, если х>1; 3) 7'(х) = х — ' 1 = ж ж ж 1, если х=1, 4) г'(х) = ~ — ] = О, если х>2; не определено, если х = О; 5) Дх) = Зх; 6) Дх) = 2з 7) )'(х) = )х/2) = то если х = 2т или х = 2т+ 1, т > О; 8) ~(х, д) = х + 2; 9) Дх, у) = х †' р = 1х — у, если х > у; 10) Дх, у) = х — у; 11) ~(х, р) = 2х+ д:, 12) 7'(х, р) = 1.15.
Построить машину Тьюринга, правильно вычисляющую функцию 1; 1) ~(х) = х — '2; 2) Дх) = ~ — ~; 3) ~(х) =— 4) Дх) = х — 5; 5) 7(хо у) = х + у; 6) 1(х, у) = — + у; 7) 1(х, у) = , 8) 11х, .у) = 1.16. По программе машины Тьюринга Т записать аналитическое выражение для функций 11х) и Дх, у), вычисляемых машиной Т (в качестве начального состояния берется ды а в качестве заключительного 9о): 2) Т: 1) Т: 4) Т; 3) Т; 13 Г. П. Гаврилов, А. А. Свпожеико 194 Гл, е'. Элемеивем галерии алеоритмое 5) Т: 1.17. Какие одноместные функции вычисляются всеми такими машинами Тьюринга в алфавите (О, 1), программы которых содержат только по одной команде? 1.18.
На решетке с шагом 1 смоделировать работу машины Т, вычисляющей функцию 1: Цу(т)=х+2, 1=2; 2) Д(х)=2 — 'т, 1=3; 3) 1(х) = —, 1 = 4: 4) 1(х) = 3 — 2х, 1 = 3; 5) Дт, д) = 2 — д, 1 = 2; б) ~(х, у) = х зк у, 1 = 3; 7) Д(т, у) = т + (у — Ц, 1 = 2. 1.19. Построить машину Тьюринга, преобразующую один машинный код в другой. Ц Заданный 1-кратный код набора преобразуется в решетчатый код (1 > 2); а) 1'0'1ж (функцнонирование машины не должно зависеть от значения Е); б) 1з'0'1'0'1з' (функционирование машины не должно зависеть от значения Ц; в) 1~0~1~0'...
0'1~ (в массивов единиц, п > Ц; рассмотреть два случая: (Ц п фиксировано, 1 произвольное, (2) 1 фиксировано, п произвольное, г) 10" е00'1' (здесь 1 фиксированное, меняотся а, а > 0). 2) Решетчатый код с заданной совокупностью слов, расположенных на соответствующих решетках (1-й, 2-й и т. д.), преобразуется в 1-кратный код с указанным значением 1; а)1, 1 "1 (аЪО), 1=2; б) 1 е1 1з 1 (о)0), 1=2; в)1 ", 1 ', 1 (а>0), 1=3. у'2. Классы ввьииелиаых ьь рекурсивных функций 195 3 2.
Классы вычнслимых и рекурсивных функций 1. Операции суперпозиции, примитивной рекурсии и минимизации. Функции, рассматриваемые в этом параграфе, являются частичными числовыми функциями. ФУнкциЯ Р(х„..., х„) = 1(дь(хп ..., х„), ..., д„,(хы ..., х„)) называется суперпозицией функций 1" и уь, ..., д,„и иногда обозначается через Я(1ььььь: д ', ..., у„, ), причем функция Е определена на наборе Пп тогда и только тогда, когда каждая функция д, определена на наборе оп и, кроме того, функция 1 определена на наборе (уь(о"), ..., д„,(о")); в этом случае г'(Пп) = Д(дь(П"),...
ут (а )) ° Пусть д(хы ..., хп — ь) и Ь(хы ..., хп — ы хп, хп, ь) . какие-либо лве функции, причем и > 2. Определим третью функцию 1(хм ... ..., х„ы хп) с помощью следующей схемы: У(х„..., хп ы 0) = д(хь, ..., х„ь), 1(х; ", х.—, у -р 1) = Ь(х, - ", х., у, 1(х, -. (1) ...,хп ыу)), 1>0. Схема (1) называется схемой прижпптвной рекурсии для функции 1(хи) по перельенной х„и задаст примитивно рекурсивное описание функции Дхп) с помощью функций д и Ь.
Говорят также, что функция1 получена из функций у и Ь с помоьцвю операции приаипьивной рекурсии по переменной хп; используют обозна |ение З" = К(у, Ь) и указывают отдельно, по какой переменной ведется рекурсия. При задании примитивно рекурсивного описания функции 1(х), зависящей от одной переменной, схема примитивной рекурсии имеет 1"(0) = а, Р(д + 1) = Ь(дь У(д)), д > О, (2) где а константа (чнсло из множества Ьь = (О, 1, 2, ...) натурального ряда с нулем). Пусть 1(хы ..., хп ы х„) (и > Ц некоторая частичная числовая функция. Определим функцию д(хы ..., хп ь, х„) следующим образом. Пусть оп = (оь, ..., оп. ь, оп) произвольный набор целых неотрицательных чисел; рассмотрим уравнение З(оьь.
ь оп — ь д) =оьь: (3) а) если уравнение (3) имеет решение до Е Х и при всех у Е ь"ьь таких. что 0 < у < уо, функция Доы ..., о„ы у) определена и ее значения отличны от пп, то полагаем д(о") = уо, б) если уравнение (3) не имеет решений в целых неотрицательных числах, то считаем, что д(П") не определено; в) если уо наименьшее целое неотрицательное решение уравнения (3) и при некотором уь Е Х и меньшем уо значение Д(оы... ..., оп ь, уь) не определено, то полагаем, что д(о") не определено. зз* 196 Гл, г'. Элементы теории алгоритмов О функции д(х"), построенной указанным способом из функции ~(ха), говоРЯт, что она полУчена из фУнкцпи 1(хы ..., хн ы хн) с пемещьнз операции мцнпмизации по переменной хп (или, короче, с помощью минимизации пе х„).
Используются следующие, обозна- чениЯ: У = Му или д(х") = Мл„у(х"), или д(х") = Р,„()(х")), или Ых") = р У(х, "., — у) = * ) Замечание. Операции примитивной рекурсии и минимизации можно применять по любым переменным, входящим в функции 1', д и Ь, но всегда нужно указывать, по каким переменным эти операции проводятся. Претпейщимн будем называть в дальнейшем следующие функции: а) в(х) = т+ 1 (функция следования); б) о(х) = 0 (нулевая функция), в) У„",(хы ..., х„) = х„, (1 < т ( и; и = 1, 2, ...) (селекторная функции или функция выбора аргуменпт). Класс Клп всех примитивно рекурсивных функций представляет собой множество всех функций, которые могут быть получены из простейших функций с помощью операций супсрпозиции и примитивной рекурсии.
Классом Л„„ всех частично рекурсивных функций называется множество всех функций, которые могут быть получены из простейших функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. Замечание. При определении классов Л„р и К„р предполагается, что при построении каждой конкретной функции соответствующие операции применяются не более чем конечное число раз (некоторые или все операции могут вообще нс применяться).
Класс К,г всех ебщерекурсивнь1х функций представляет собой множество всех всюду определенных частично рекурсивных функций. Нетрудно показать, что Кьр с К,ю (включение строгое). Справедливо также и строгое включение К„„с Кои (т. е, существуют общерекурсивные функции, не являющиеся примитивно рекурсивными) .
Через К, будем обозначать класс всех частичных числовых функций, вычисламых на машинах Тьюринга. Т е о р е м а (о представлении вычислимых функций в специальной форме, аналог теоремы С. К. Клини о нормальной форме частично рекурсивных функций). Для всякой вычислимей функции ~(хы..., х„) существуют такие примитивно рекурсивные функции Фу(хы... ..., х„,. хилз) и Су(х~,...., хн, х,е з), чгпо Пхз хл) = Фг(х1 хм Ря1Сг(хз . хл У) = 0)). Здесь рн(С1(х~,...., хн, у) = 0) — минимальное целое неотрицательное реп|ение уравнения Су(хы ..., хлл у) = 0 (для каждого набора значений переменных хы ..., х„); если при заданном наборе (хы..., хе ) решения нет, то р„(Су(х~,....., хв, у) = 0) не определено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
