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