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