Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 38
Текст из файла (страница 38)
Операции над машинами Тьюринга. Пусть машины Т» и Т2 имен>т соответственно программы П» и П2. Предположим, что внутренние алфавиты этих машин не пересекаются и что до -- некоторое заключительное состояние машины Т„а д," какое-либо начальное состояние машины Т2. Заменим всюду в программе П» состояние д' на состояние д" и полученную программу объединим с программой П2.
Новая программа П определяет машину Т, называемую комиозииией кашин Т» и Т2 (по паре состояний (д'„, д")) и обозначаемую через Т, оТ2 или Т,Т2 (более подробно: Т = Т(Т», Тз, Щ, д"))). Внешний алфавит ком»юзицин Т,Т2 является объединением внешних алфавитов машин Т, и Т2. Пусть д' -- некоторое заключителыюе состояние машины Т., а ди какое-либо состояние машины Т, не являющееся заключительным.
Заменим всюду в программе П машины Т символ д' на д". Получим программу П', определяющую машину Т'1д', ди). Машина Т' называется итерааигй машины Т (по пара состояний (д', ди)). Пусть машины Тьюринга Т„Т2 и Тз задаются программами П», П2 и Пз соответственно.
Считаем, что внутренние алфавиты этих машин попарно не пересекаются. Пусть д' и д" — какие-либо различные заключительные состояния машины Т». Заменим всюду в программе П» состояние д' некоторым начш»ьным состоянием д', машины Т2, а состояние д" некоторым начальным состоянием д" машины Тз. Затем новую программу объединим с программами П2 и Пз. Получим программу П, задан»щую машину Тьюринга Т = Т(Т», (д', д'), Т2, (д~о', д»), Тз).
Эта машина называется разве»лвленигм маи»ин "12 и Тз уиравлягмь»м ма»виной Т,. При задании сложных машин Тьюринга часто применяя»т так называемую операторную запись алгоритма, которая представляет собой строку, состоящую из символов, обозначающих машины, символов перехода (вида ~~' и до~ ), а также символов <» и и», служаь п»их для обозначения соответственно начала и окончания работы алгоритма. В операторной записи (некоторого алгоритма) выражение Т, Ц,~Т ...Т д„~~Ти обозначает разветвленио машин Т и Т„, 1 ь управляемое машиной Т„причем заключительное состояние д,о машины Т, заменяется начальным состоянием дш машины Ти, а всякос другое заключительное состояние машины Т, заменяется начальным состоянием машины Т (одним и тем же).
Если машина Т, имеет одно заключительное состояние, то символы ~~,о и д„»~ служат для обозначения безусловного перехода. Там, где не могут возникнуть недоразумения, символы д,о и д„» опускаются. Пример 3. Операторная схема )Т»<»Т2 )дзо Тз (дзо Тви» 2 1 2 описывает следующий <<процесс вычисления». Начинает работу машина Тз. Если она заканчивает работу в состоянии дзо, то начинает ~ б Машины Тьюринеа и операции над ниии 187 работать машина Т„а по окончании работы машины Т, вновь «выполняет работу» машина Тз.
Если же машина Тз останавливается в некотоРом заключительном состоЯнии, отличном от е7за, то «РаботУ продолжает» машина Тз. Если Тз приходит в заключительное состоЯние азо, то начинает РаботУ машина ТН если же Тз заканчивает Работу в некотором заключительном состоянии, отличном от дзе, то «работу продолжает» машина Та. Если машина Та когда-либо остановится, то процесс вычисления на этом заканчивается. 1.9. Построить композицию Т1 Тз машин Тьюринга Т1 и Тз по паре состояний (ц~е, азз) и найти результат применения композиции Т, Тз к слову Р (дза - заключительное состояние машины Тз); 1) Т,: Т: ) Р 130212, б) Р 1401. 2) Тб Т: а) Р = 1'0'1'01' б) Р = 1з ~01) з 1з. 1.10. Найти результат применения итерации машины Т по паре состояний (це, ц,) к слову Р (заключительными состояниями являются яа н Че) 1)1=1, Т: а) Р 1зь.
б) Р 1зьтп в) Р 1зь+з ~й > Ц. 2)1=1, Т: а) Р 1за. б) Р 1заез („. > Ц. 188 Гл. К Элемеиты теории алгоритмов 3) 1=3, Т: Р = 1'01о (т > 1, у > 1). 1.11. Найти результат применения машины Т = Т(Тм (Чзо, Чм), (Ч10; Чзз) Тз) к слову Р (Чзо заключительное состояние машины Тз, а Чзе —.. заключительное состоЯние машины Тз): Т: ;) Р=ЦЦз б) Р=1збР 2) Т,: а) Р = 1ебг1 (т > 1); б) Р = 1"0101"01е (х > 1, у > 1, г > 1). 1.12. Используя машины Т„Тз, Тз, Та и Тз, построить операторную схему алгоритма й (здесь Чзо, Чзе, Чге, Чзе, Чво, Чее и Ч;о заключительные состояния соответствующих машин): Т: Тз.
189 Э Н Машины Тьюринеа и операции над ниии Тз .' 1) Й: Чг1а ~ — Чо1га (т > 0); 2) й: Чг1а+~ ~ — Чо1за (л > Ц, 3) й: И'ОЧг1ае г ! —. И'ОЧо1гаег (т > 0). 1.13. По операторной схеме алгоритма л и описанию машин, входящих в нее, построить программу машины Т, задаваемой этой схемой, и найти результат применения машины Т к слову Р: 1) Й = оТ1 ) ТгТз 1Чзо ог, , Т: Р = 1*01" (т > 1, д > 1).
(начальные состоЯниЯ машин Чы, Чгг и Чзы а заключительные "- Чщ, Чго; Чзо и Чзо)~ 2) й = о ~ ТгТг ~Чго Тз ~Чзо г Тг.. Тз. Т; Р=1'01" (и>1,у>1) (начальные состоиниЯ машин Чы, Чгз и Чзм а заключительные ЧгО Чго Чго Чзо и Чзо) 190 Гл. К Элвмгнты твории алгоритмов 3. Вычислимые функции. Пусть И = (оы оз, ..., о„) (и > 1) произвольный набор целых неотрицательных чисел.
Слово 1о'л«01а'т«0...01а л' называется основным, машинным кодом (или просто кодом) набора П (в алфавите (О, 1)) и обозначается ь(а). В частности, слово 1 вз является основным машинным кодом числа сс В дальнейшем рассматриваются частичные числовые функции. Функция ДтТ«) (п > 1) называется частичной числовой функцией, если переменные ац принимают значения из натурального ряда с нулем; Х = (О, 1, 2, ..., т, ...), и в том случае, когда на наборе о" = (оь, оз, ....
ол) функция 1 определена. 1(п") 6 Ж. Частичная числовая функция д(аа) называется вычислимой (но Тьюрингу), если существует машина Тьюринга Ту, обладающая следующими свойствами: а) если т"(о") определено, то Т1(й(о")) = й(1(ол)); б) если До") не определено, то либо Ту(а(П")) не является кодом никакого числа из Х, либо машина Т1 не применима к слову 1«(о о). Замечание. В дальнейшем предполагаем, что в начальный момент головка машины обозревает самую левую единицу слова й(Па). Известно, что это ограничение не сужает класса вычислимых функций. Если функция 1" вычислима по Тьюрингу с помощью машины Ту, то будем говорить, что машина Т1 вычисл«ет функцию у. Говорят, что машина Тьюринга Т правильно вычисляет функцию 1(та), если: а) в случае, когда у(ао) определено, машина Т, начав работу с левой единицы кода а(П"), останавливается, Т(й(П")) = н(Да")) и головка машины в заключительной конфигурации обозревает левую единицу кода йО (П")); б) в случае, когда Д~ао) не определено, машина Т, начав работу с левой единицы кода й(И"), не останавливается.
Справедливо следующее утверждение: дл«всякой вычислимой функции существует машина Тьюрингщ правильно вычисляюща« эту функцию. Расстояние между двумя «чейнами С и С' ленты равно увеличенному на единицу числу ячеек, расположенных между С и С'. В частности, соседние ячейки ленты находятся друг от друга на расстоянии 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) можно построить машину Тьюринга, преобразующую основной код любого набора о" в его решетчатпый код, а также можно построить машину Тьюринга, преобразующую решетчитый код всякого набора Пь в его основной код.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
