В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 21
Текст из файла (страница 21)
эом постросниык функций. Воспшп,чуемся специальным кодированием натуральнык, чисел в алфаанге ((): каждое натуральное чпсло представим (л .1- 1) симвплом (, т. е. числа О, 1, 2,... кодируем слоаамн (, Н (()'" Частичная числовая и-местная функция ((ль..., х ) казы. вастся сычислилод яо Уьюринзр, сели сущестаует машина М, вы шсляю~цэя ее в следующем смысле: 1. Если набор значений аргументов <ль..., л ) прапад.
лежит области определения функции Е то мпгнина М, начинан работу в конфигурации О (с+' О (о+'...О— (1.18) ш (где (* ( .. ( и эпспринимается самый правый снмаол (), останавливается, заканчива» работу в конфигурации где р = ((ль. °, л ).
2. Есл» набор значений аргументоа <хь..., л ) не принадлежит области определения функции Е то машина М. нач~) ная работу в конфигурации (1.18), работает бесконечно, т. е не прпхолит в ааключительное состояние. Пример 1АО. Простейшие функции 8(л) л+1 и 0(х) ! аычислимы ио Тьюркнгу. Первую из аих вычисляет машина М„ описанная а примере 1.38, а вторую — машина с теми же аз' фавитамн и программой ф( 4 81. 4,8 4,(С. Можно доказать, что любая частично рекурсивная фун шш вычислнма по Тьюрннгу и, наоборот, любая эычислимая я) Тьюрингу функция частично рекурсиеиа.
Теперь, обладая точным формальным понятием алгоритма мы можем доказать неразрешимость нскоторык алгорптмя'и скок проблем. Каждая машина Тьюринга по определению есть кайф (1.17), т. е. задается внешним алфавитом А (!.14), аафааита ииутрелннк состояний 14 (1.15) и программой П: б,„ат;ьб,.а,,БЫ.
а 1,..., й, (1.19' где 5~ — это й; Зз — это С; Зз — это С. При этом можно сй тать, что существуют некоторые обширные алфавиты А, и мр в которых записываются символы (1.!4) н (!.15) для всех еа шин Тьюринга. Тогда енино«ы рь, агч )гш лм из (129) есть снмвпаы алфавитов Ат и !2г. Уках ем способ нуиерацни всех пашни Тьюринга (гсдсзсва нумерация). Пусть рь рь рз.. — нослелователыюсгь всех простых чисел, расиологкешгых а порви е зозрастаии» (т. е. последовательность 2, 3, б, 7, !1...). Номером машины Тьюринга ,!! с программой (1.19) назовем числа Л (М) = в!му т)ГЬР* пут(яцгттр Ч)НЧ(юге... I, ". Р; Рй з Рй з Рм, Рм ° Пример 1А1.
Номер пашням Мг, описанной в примере 139лю число н(М,) 2' 3' 5' 7< 1!' 13' Бч 19' 23' 29з. Естественно. что ис все натуральныс числа нвляктся и»пе- рез ч машин Тьюринга. Если и — помер не«спорой машины в алфавнгат (1.14), (1.13). то се программу можно однозначно восстаиовить по этому номеру. Как н раньше, «одируем натуральныс числа симаолач Буде» рассматривать машины Тыорингш алфавгп коюрых со- держит символ ). Наппминм, что машина называется прнмытимой к начальни- ку г. ову, если она, начав работать с зпш свозом на ленте, нрндет в заключительное состояние.
Машина М, ирна снима» к слову л(М) (т. е. к коду своего ссбствсш~шо шшсра), называстс» солонрнлекшюв. Мишина, не применимая к алоач н(М), называется нзсилопрвзгенпгюй. Машина М~ !гм, крамер !.38) свмопримениыа. Прниерем и«саионрвменнмой нинины является машина, в кривых частях коиагш которой на встречаются залюочнгелыгые состояния. Та«а» машина нс и»имен«из ни к какому слову. Следу» О. Б. Лупапову ', рассмотрпи алгоритмическую нроблелр сшчонримени ости Опа гостонт в следу«коси: ука- зать алгор«тм, шиорый па любой машвнс Тьюринга устаивал»- ааз бы, сзмопрпменвна пяа нлн ист. Со«лат!го тезису Тьюринга такой алгоритм следует «снять в анде машины Тьюринга, т.
е. требуетсе построить машину Тьюринга, «оторва была бм применима к «одам нокеров всех чашки.Тьюринга н в зависимости от топь самоф имевииа она иле иет, иыела бы равлпчвые заключительные копфягурации. Пусть, например, в случае самапримыгимий машины заключз- тельпйя конфнгурацяя кисет вид ! е Си: Лукаш О. В цене« к .е ма камна ш а М М л. Мту, 1ШО, т Ю где вне обозреаасмой ячейки могут быть записаны какие уг но символы алфавита, а в случае нссамоприменпмай машкам' у од. заклгочнтельная конфигурадня имеет вид о чь не Теорема 1.23. Проблема самолрименимасги алзоритмичес разрешима, ю е. не существует машины Тьюринга, решающей ки зту проблему е указанном еыше сл.ьиее.
Допустим, что такая машина А существует. Тогда можно построить машину В, которая 1) применима ко всем кодаи номеров несамоприменимых машин и 2) не ирвыенима ко всем кодам номеров самопримеивмых машин. Действительно, машина В получается нз машины А следую. шны образом: алфавит сохраняется неизменным, заключвтсльное састояняе уь машяны А считается незаключительпым состоянием машины В, а заключительпыы состоянием машины В считается новое состопиие 0'ь. Програыма машины В состоят из всех комаяд машины А н еше двух иоманд: уь1-ьуь1С; уьб-ьд ьОС. Очевилио, что машина В удовлетворяет требоваивяи1и2.
Сача машина В либо самоиримеиима. либо несамопрямеивма. Есан она самоприменима, т. е. применима к коду сваегз намерз, то она применима я к колу самапримеинмой ыаюины, но тогда не выполняется требование 2. Если машина В несамопримснпма, т. е. нс применима к ко. ду своего номера, то она не применима я к коду песамапримег пимой машины, но тогда ие выполняется трсбоваяпе 1. Итак, ыы пришли к противоречию. основываясь на допуще-, нии о том, что существует машина А, решаюшаи проблему самопримснимссти. Следовательно, такой машины не существует.
Заметим, чта неразрешима именно массовая праблеызг не сушествует единого алгоритма, который решал бы яроблеиу самоприменимости. Мы же приводили примеры конкретиык машин Тьюривга, длп которых такой алгоритм сушествует. Используя результат теоремы 1.23, можно докааать неразрешимость других алгоритмических проблем. Рассмотрим, на-" пример, проблему применимости н начальному славу.
Она со: стоит в следующем: указать алгоритм, кашрый по машине М з слову Х устанавливал бы, применима машива М к славу Х илв' пет. В терминах машин Тьюринга зту проблеиу можно сфоР мулвровать так: можно ли построить машину, которая была бп вримеиима ка всем словам вида п(М)ОХ, где М вЂ” праизвазн иая машина, Х вЂ” произвольное славы в в случае, если машияз М прмыеннма к слову Х, привгшила бы к закаючительной км)1 фигурвшш ! Чь 100 а е случац села машина М ве прнменпиа к слову Х, приведшая бы к заключительной копфнгУРзцнн О ч Узорсма 1.24, У(роблели прк г алости х начально.еу слоев езгоритизшчески лерсзрешвмщ г.
з. ие сущсстеуег лишили узариига, регииющеп згу лробхелу е укиаилиол езиие смысле. Допустнм, что такая машпяа О сутцествует. Пусть Š— маюггнз, удванвающзя слова (см. промер 1.Зб). Рассмотрнм машкну б, которан является компознцней машин Е н О.
Если в начальный момент работы яншины 6 на ленте будет слово л(М), то после работы машины Е на ленте будет слово и(М)бп(М). Машина 0 применима ко всем таким словам и остановятся в конфнгурацнп е есля машина М применима к слову л(М), н в конфнсурацнн О чч есле машина М не применима к слову л(М). На тогда машина 6 решает проблему самоярнменнмосги, что невозможно в силу теорамы 1.2З. 14так, мы пришлы к прсчкваречпю, исходя нз допущения. что существует машина, решающая проблему применимости.
Следовательно, такой машины яе существует. Задачи п улражневня 1. Доказать прямнтнвную рекурспвность следующих функций: а) )(х) х + й; б) Дх. д) .ту; в) )(х, у) = пцп(х, д); г) !(х, у) шах(т, у). 2. Доказать, что всякая прпм~гтивяо-рекурсивная функцля общ рекурспвна. 3 Доказать, что следующие функция частично рекурсивны: а) ннгде пе определенная функция м, т. е. функция ы с пустой областью определенна; б) )(х —:у) = ! х)д, ~~ д " (не определена в остальных случаях.
4 Построить машины Тьюринга, вычисляющие функции: а) Дх) х + й; б) ! (х, д) = х + сб в) Цх) = х —; 1. га! АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ ГЛАВА 2 Приведем краткое наложение основных понитий теории алгебраических струнтур (групп, колец п повей). Проиллюстрируем также приложение теоретико-групповых методов к одной нз задач теории пнфорыацни; порождению, кодированию и декоднроваипютруоповых кодов. 2«й ГРУППЫ 2.1.!. Полугруппы я мононды Множество П с заданной в ием бинарной ассоциативной опера цпей называется лозрггруапой, Полугруппа с единичным злеиснтом ггазывмтся з:опопдол (илп просто полутрупной с единицеп). Пример 2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
