Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 37
Текст из файла (страница 37)
Аналогично рассматривается случай с нечетным первым единичным массивом. 183 1 д Машины Тьюринга и операции над ниии Подходящая машина задается программой Чг1Чг1Л Чз1Ч41Л Чг1Ч41Л Ч41Чз1Л ч,оч,ол ч,оч,ол ЧгОЧ40Л Ч,1Ч,ОЛ Чг ОЧе1о ЧгОЧг1Ь 2) П.
Ч41Чг1Л а) Р = 1'Ог1; Чг1Ч11Л б) Р = 14; в) Р = 1г01з; Ч10Чг1Л ЧгОЧЗ 1 Л Чг1ЧЗОЛ Чз1Ч41Л Ч,ОЧ,1Л Ч,1Ч,ОЛ Ч,ОЧ, 1Л Чг1Ч31-о ЧзОЧ, 1.~, а) Р = 1зЩг. б) Р = 14. в) Р 1г[01)г. 3) П: а) Р = [10)г1;. б) Р 10г1г. ) Р 10з1. 4) П: Ч10Чг1Л Ч41Чг1Л а) Р =1' б) Р = 1'0'1 в) Р =10'1. Чг1Ч401, ЧзОЧг1Л Чз1ЧоОА 5) П: 1.2. Построить в алфавите 10, 1) машину Тьюринга, обладающую следующими свойствами [предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0): 1) машина имеет одно состояние, одну команду и применима к любому слову в алфавите 10, 1); 1.1.
Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р. Предполагается, что Чг начальное состоЯние, Че заключительное состоЯние и в начальный момент головка машины обозревает самую левую единицу на ленте: ч,оч,ол 1) П: Ч,1Ч,ОЛ а) Р = 1з01; б) Р = 1гог1. в) Р = 1е: 184 Гл. 1е. Элементы теорем алгоритмов 2) машина имеет две команды, не применима ни к какому слову в алфавите (О, 1) и зона работы на каждом слове бесконечная; 3) машина имеет две команды, не применима ни к какому слову в алфавите (О, 1) и зона работы на любом слове ограничена одним и тем же числом ячеек, нс зависящим от выбранного слова; 4) машина имеет три команды, применима к словам 102м1 (и ) 1) и не применима к словам 102в+ 1 (и > 0); 5) машина имеет пять команд, применима к словам 12" (и ) 1) и не применима к словам 12"+е (о = 1, 2 и и ) 0); 6) машина применима к словам 1м01", где и > 1, и не применима к словам 1"'01", где ие ~ и, т ) 1 и и > 1.
1.3. По заданной машине Тьюринга Т и начальной конфигурации К1 найти заключительную конфигурацию (Чо -- заключительное состояние); Ч,ОЧ,1Л 1) Т. 0 1о а) К1 = 1201Ч11г. б) К1 101Ч1012 Ч2 Чо Ч2 1Ч1 11' Ч,ОЧ,Ы Ч11Ч21К а) К1 = 1Ч101; б) К1 = 1Ч11; з. л. Чг 1Ч1 ОЛ Ч,ОЧ.ОТ, 2) Т: Ч,ОЧ,ОТ, Ч, 1Ч,ОЛ Ч20Ч21А Ч21ЧоОК а) К1 10зЧ101.
б) К1 1гЧ11з01 Ч1 ОЧо1~ Ч1 Чг ) К 12 1201. б) К 1 14. Ч,ОЧ,ОЛ Ч2 1Ч2 1е 4) Т: Ч,ОЧ,ОЯ Ч1 1 Чг 1 -' е Ч20Чо11 в. 3 4 Ч21Ч,ОЛ а) К1 = 1Ч11': б) К1 = Ч11 01; в) К1 = 10Ч11 . Ч,ОЧ,11, Ч,1Ч,ОК 5) Т: 1.4. Построить в алфавите (О, 1) машину Тьюринга, переводящую конфигурации К1 в конфигурации Ко1.
1) К1 = Ч11 Ко = Чо1 01 (и ) 1)' 2) К1 = Ч10" 1", Ко = Чо[01)м (и, > Ц; 1 5 Машины Тошринеа и операции над ниии 185 3) Кз = 1"410, Ко = цо1'" ?и > 1); 4) К1 =1"4101п', Ко = 1 до01" (гп > 1, п > 1). 1.5. 1) Показать, что для всякой машины Тьюринга существует эквивалентная ей машина, в программе которой отсутствует символ Я. 2) Показать, что по всякой машине Тьюринга можно построить эквивалентную ей машину, в программе которой не содержится заключительных состояний. 1.6. Показать, что для всякой машины Тьюринга Т в алфавите А существует счетно-бесконочное множество эквивалентных ей машин Т„рз, ..., Т„„...
в том же алфавите А, отличающихся друг от друга своими программами. 1.7. Сколько существует неэквивалентных машин Тьюринга в алфавите 10, 1), программы которых содержат только по одной командеу 1.8. По словесному описанию машины Тьюринга построить ее программу (в алфавите 10, 1)). 1) Начав работу с последней единицы массива из единиц, машина «сдвигает» его на одну ячейку влево, не изменяя «остального содержимого» ленты. Головка останавливается на первой единице «перенесенного» массива. 2) Начав двигаться вправо от какой-то «начальной» ячейки, головка «находит» первую при таком перемещении ячейку с единицей (если такая ячейка «встретится на пути») и, сделав «один шаг» вправо, останавливается на соседней ячейке.
Если в «начальной» ячейке записана единица, то головка останавливается на соседней справа ячейке. Содержимое ленты не меняется. 3) Машина начинает работу с самой левой непустой ячейки и отыскивает единицу., примыкающую с левой стороны к первому слева массиву из трех нулей («окаймленному» единицами). Головка останавливается на найденной единице (если такая есть). Содержимое ленты не меняется. 4) При заданном 1 > 1 головка машины, начав работу с произвольной ячейки, содержащей единицу, двигается вправо до тех пор, пока не пройдет подряд ? + 1 нулей. Головка останавливается на первой ячейке за этими 1 + 1 нулями, напечатав в ней 1.
Остальное содержимое ленты не меняется. 5) При заданном ? > 1 головка машины, начав работу с какой-то ячейки и двигаясь вправо, ставит подряд 2? единиц и останавливается на последней из них. 6) При заданном 1 > 1 головка машины, двигаясь вправо от какой- либо пустой ячейки, находит первый при таком перемещении массив, содержащий не менее ? единиц, стирает в нем первые 1 единиц и останавливается на самой правой из ячеек, в которых были стертые единицы.
Остальное содержимое ленты не меняется. 186 Гл. К Элвмен»пь» теории алгоритмов 2. Операции над машинами Тьюринга. Пусть машины Т» и Т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(та), если: а) в случае, когда у(ао) определено, машина Т, начав работу с левой единицы кода к(П"), останавливается, Т(й(П")) = а(Да")) и головка машины в заключительной конфигурации обозревает левую единицу кода йО (П")); б) в случае, когда Д~ан) не определено, машина Т, начав работу с левой единицы кода й(И"), не останавливается. Справедливо следующее утверждение: дл«всякой вычислимой функции существует машина Тьюрингщ правильно вычисляюща« эту функцию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
