Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 38
Текст из файла (страница 38)
Расстояние между двумя «чейнами С и С' ленты равно увеличенному на единицу числу ячеек, расположенных между С и С'. В частности, соседние ячейки ленты находятся друг от друга на расстоянии 1. Пусть | —. целое положительное число. Подмножество всех таких ячеек ленты, каждые две из которых расположены друг от друга на расстоянии, кратном 1, называется решеткой с шагом й Ленту можно рассматривать как объединение 1 решеток с шагом 1. Пусть Л~б -- решетка с шагом ) Пве ячейки этой решетки называются соседними, если расстояние между ними, рассматриваемое относительно всей ленты, равно й Говорят, что слово Р = а,аз...а записано на решетке Л~б, если: символ аз записан в некоторой ячейке Сь этой решетки; 1 Д Машины Тьюринга и опервции над ними 191 символ аз записан в ячейке Сз, которая является соседней к Сг на решетке Л~б и расположена справа от нее и т.
дц символ а,„записан в ячейке С, отстоящей от ячейки Сз на расстояние (еп — 1) 1 и расположенной справа от См Будем говорить, что мишина Тьюринга Тз моделирует .машину Тьюринга Т на решетке В10 (с шагом 1), если, каково бы ни было слово Р (в алфавите А),. выполняется следукьщее условие: пусть на решетке Лд~ записано слово Р и в начальный момент головка машины Т| обозревает самую левую букву слова Р, машина Т, останавливается тогда и только тогда, когда машина Т применима к слову Р; при этом, если Т(Р) определено, то после окончания работы машины Т1 на решетке Лд будет записано слово Т(Р). Справедливо следующее утверждение: для каждой маигины Тьюринга Т и каждой решетки Л~б с шагом 1 можно построить машину Тьюринга Тм моделирун~и1ую машину Тьюринга Т на решелпке Лйб.
Пусть ои = (оы ог, ..., оп) (п > 1) -- произвольный набор целых неотрицательных чисел; 1-крагпным кодом этого набора называется слово в алфавите (О, 1), имеющее вид 10 '»ПО'10 а+00'... 010---П (1>2) Справедливо утверждение: для каждого фиксированного целого числа и (п > 1) существует машина Тьюринга, преобразующая основной код любого набора сг" в его Бкратпный код, а гпакже сущетпвует маизина Тьюринга, преобразующая1-крапьный код всякого набора а" в его основной код. Решетчатым кодом набора а" = (ом ог, ..., оп) (п > 1) называется слово в алфавите (О, 1), записанное на п решетках с шагом п, причем так, что на первой решетке записано слово 1 '+~, на второй слово 1"'"' и т.д., на и-й слово 1 "+',. начала слов на решетках должны быть согласованы, т.
е, самая левая единица на первой решетке непосредственно предшествует (на всей ленте) самой левой единице на второй решетке, а эта единица непосредственно предшествует самой левой единице на третьей решетке и т.д. Справедливо утверждение: для всякого фиксированного целого числа п (п > 1) можно построить машину Тьюринга, преобразующую основной код любого набора о" в его решетчатпый код, а также можно построить машину Тьюринга, преобразующую решетчатый код всякого набора Пь в его основной код. П р н м е р 4.
Зля функции 1 (г) = 2г — 1 построить машину Тьюринга, вычисляющую ее, а также машину Тьюринга, правильно вычисляющую эту функцию. Замечание. Здесь и в дальнейшем при «аналитическом» задании числовых функций используются известные (из математического анализа) «элементарные» функции. При этом «аналитичсски» заданная функция считается определенной только на таких целочисленных наборах значений переменных (принадлежащих множеству 1ч' натуральному ряду с нулем), на которых определены и принимают 192 Гл. К Элементы еаеории алгоритмов целые неотрицательные значения все «элсментарные» функции, вхо- дящие в рассматриваемое «формульное задание» определяемой функ» ции. Например, функция определена лишь тогда, когда — —.
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(хи) по перельенной х„и задаст примитивно рекурсивное описание функции Дхп) с помощью функций д и Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
