В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 20
Текст из файла (страница 20)
где а — коистаита. Заметим, что схема првмипрвиой рекурсия (!.13) полностью определяет фуикцвю ф ээ функция )(хь..., х ) называется яримитиеио-ренррсизноф если оиа мпжст быть получена нз прпстейшнк функций с помо. щью конечного числа применений операторов суперпозиции (1.!2) м примитивной рекурсии (1.13).
Пример 1.Па. Следующие функции ирнмятивно-рекурсизиы: а) 5(х), 0(х), ! (хь ..., х ); б) фуакцня 0(хь..., х„) = О, так как 0(хь..., х„) = 0(1~(хь..., х„)), т. е. оиа получена нз простейших функций 0(х) н 1~ (кь ° °, х„) с помощью оператора суперпазнцни; в) )[х) х+ л, т.е. )(х) =5(5(... 5(х))...); г) ((х. р) = х + р. Действительно, ( . ) (к. 0) = к + 0 = х = Д (х); )(к р + !) х + (р + 1) (х + р) + 1 5(х + р), т. е. Дх, р) = х + р пплучеив нз примитивно-(юкурснвнык функ- цнб п(х) Д(х) н ф(х, у, х) а+! 5(а) с помощью опера- тора првмитианой рекурсии. Э. Сггыратор мияимизоцпи (П-оператор).
Говорят, что функ- циа )(хь ..., х ) полУчена из фУнкции 5(хь ..., х„, Р) с пп- мпщью оператора милииизпции (или просто П-оператора) и обозначают )(хь ..., х ) рр(5(хь ..., х, у) - 0), если )(хи ° ., к ) определена и равна р тогда и тилько тогда, ногла 5(к,,..., х, 0),..., 5(хь,.., хч, р — !) определены и не рав. ны О, а 5(х...., х у) = О. Функция ((хь..., х„) называется частичке рскррагеяоб, ес- ли она может быть получена из простейших функций с помо- гпью конечипго числа применений операторов суперпозкцян, примитивной рекурсии н минимизации. Всюду определенные частично рекурсивные функции называются общерекурсиелыми. Пример !57.
рассмотрим функпию х — р, если х *д; ((~ р) ~ нс определена в остальных случаях. Покажем, что она частички рекурсивна. Виснем вспомогатель- ные функции: к — 1, если х)1; О,велик 0; к — р,солих р; ) — р= О,солих(у. Этн функции примитивно-рекурсианы. Действительно, ( Π— '1 О=О(х); (0+1) — 1-р-! 1,(х, р, х); (: к — '0 х; к —. (у + 1) = (х — у],—:.1. Тогда функция )х — у) (х — р) -1. (р — 'х) также примитивнорскурсивгга. Пусть д(х, р, а) )х — (э+р)). Эта функции примитивно-рекурсиипа. Функция )(х, р) может быть ппдучепа гш нее с помощью а»оратора миггйлгггзацни: Цх, р) = Ых()х — (х+ +р) ) =О), и, сасдоватехьио, она частично рскурсивна.
А. Черч выдвинул слетуюшую гнпотеэу. Тезис Черча. Всякая эффект»в»о вычпсхпяая функции »ах»его» яасгпчио»екург напои В г)юрмуаирпвку тезиса Черча вход»т интуитивное понятие эффектишгпй выч»схимостн. поэтому его ггсаьэя ни докаэать, ни опровергнуть в общепринятом математическом смысле. Это иелоторый факт, в пользу которого говорит многолетняя математическая практика. Частична» рек!рсивносгь — это уточнение понятия вычисхкмой функции. С помощью этого точгюго опрелеаени» можно дон»ты»ать наи опровергать »ычисхпмостк Наряду с частичной рскурспвностью имеются и дртгие утпчиенин ноияюгя иычисх»- мой функции (нанрныер, понятие эычислимоств по Тьюрингу).
Л1шкио доказать нк эквивалентиостк 1.02. Машиггы Тьюринга Л(ашик» Тьюринга — это математическая модель ггдеахизвроваппого »ми»сиятельного устройства. Приае.гем сначала неформальное ее опнсаиаег !. Пусть имеется хентэ, т. с. ноаоса. разбитая иа конечное число нчеек. В каждой ячейке лепты в каждый момент времени »вписан один иэ симеонов па «ь..., а,.
(1.(э) Совокупность этих символов иаэывэется виши»им алфавитом машины. Снмвоа а, — »ушай (егп обычна обоэпачают снмво. хоы О). В аргщегсе работы машины к существующим ячейкам мыут пристраиваться иоана пустые »чейни, так что хант) можно счвтать неограниченной е обе стороны. 2.
Каждая мишина сбхадает внутренней иан»тью, которая мохгет находнтьс» а конечном числе спстояшш, Спстояиил внут. ренисй памяти обознэчэгог символами (1.10) Рь йь..., Э отхичнымн от символов (!.14), и иаэывают внутренними состоя. пнями машинм. Одно из таких состояний (обычно Сг) на»ма»юг эакаючитокьным, а другое (обычно ф) — начальным. 3. Иьгшяся упраеаяющая гоховка, которая нижет игрене. гкшься вдоль ленты такии образам, что в каждый момент времени оиа находится в окредехенпоб ячейке хситы.
Привыа го. ворить, что машина воспринимает шу ячейлу. Шшнчи действуег нс непрерывно, а лишь в дискретные момсйпч времени. щ В завнсимсст«от вкугренвегп состояния в от символа, залпов«кого на впсщншимаемой ячейке, в следующий момент времени машк«а першюлнт в новое внутреннее состоя«ие (воз«оп«о в то же самое), записывает новый символ в ту жс нчейку (воэможво, тот же самый) п либо сдвигает управляющую головку иа одну клетку влево илв вправо, либо оставляет ее па месте. Если упраааянхцая головка воспршгемает самую правую (левую) ячейку, а машнва по ходу работы должна слвпауть гпловку в отсутствующую ячейку справа (слева), то она прястранвает недостающую ячсику. Попав в заключительное сссгоянгге, машина прекращает рабглу. КонФигурацией на ленте (или машинным словом) называ«ю« совокупность, образовапнаяг 1) последователыкмтью аг,, ог,,..., и симеплов, «алиев«- ни» в ячейках лшпы, где ап — ей«вод записанный в переой ячейке Слева, ай — символ, зал«с«паяй во втпрой ячейке слева, а т.
д. (любая такая послсдпвателгмссть вазывается словом в алфавпте (1.14) ); 2) состоянием внутренней памяти йй 3 номером й «сспр«нимаемой ячеййи. снф«гурацию машины будем записывать такг ч '"' е Так как «аждая машгша «моет «онечиый алфавит п кшгеч. нос числа внутренних состоя«ей, то яз описания се рампы мщпо, что ова может выполнять конеч«о» число действий. Если машина, находясь во внутреннем ссслзшигг уг н всспрннпиая ячейку с с«мволом аг, записывает к слелующему момегпу времени а зту ячейку симеон и переходит во внутре«нее состояние 4 и сдвигается пп лепте, то творят, что машина вы.
полияет пемз«ду рш бш 5. (1.16) тле 5 — сленг. Вместо 5 будем писать букву У, егия слвяг ссуществляется влево, бугшу Я, если сдвиг прписходвт вправо, н С, если головка остается на месте. Прн этою мппрят, что измена переводит конфпгурацюо иг ... аг, †' оаы ... аг . тле «г ,ое и ив о — произвольные слоев в алфавпте (1.14), в нонбжгурацию аг... г'и,и ... и;и г ип..
г,.,иь -' — "' ... иг нли иги., иг — 'а ... а а завис«моста и, ог того,' какое значение принимает сдвиг в «ома«де. Совокупность асех команд, которые может выполнять ма. шнна, назынается ее программпй. Прпграмма мапшны должна содержать одну н только одну команду, пач~шающуюся слоном Шаг, 1=1, ..., ш, 1 О, 1, ..., л. Кажлая машина Тьюрннга определяется свопм алфавнтпм, состояниями внутренней памяти н прпграммпй. Чтобы полностью опрсделнть работу машнны, надо указать Ее копфнгурацяю лля пачальнпго момента времени.
Будем счн. тать, чтп в начальнОЙ конфнгурагтг~н гплозка зпспрннпмает сам правую непустую 'ячейку. ((ю так, машина Уьюршма есть, по определенню, набор М = <Д. а 11>, (13 7) где А — внешней алфавит (1.14) с выдетенным пустым символом пег 1'1 — алфавит вяутренннх ссстоянпй (1.131 с выдсленнымн символами конечного н начальпогп состояний ш н р; П— программа, т. е, конечная последовательность упорядоченных пятерпк скмеелоз (1дб).
Если машпна, начав работу с некоторым слоном, записан. ным на ленте, прндет е заключительное состоянае, то она называется ярилелямоб к атому слову. Рсзультатпм ее работы считается слоап, запясанное на ленте з заключательном спстояпае. Если же машана ня а какой момент аременц не прядет в заключптельппе ыктоянне, то опа называется ле лрллеяялой к даннпму слпву, а результат ее работы не определен.
Прммер 1.33. Рассмотрим машнну М, с внешним алфапптом (О, )), двумя внутренними состояннямц (дь ш) и программой ш)- чг)Е: Машина М, выполняет следующую операцнюг к любому слпзу, иютояшему пз символов ), она пркбавляст еще один снмеол ) я останавливается. Если, например, в начальпоы спсгоянця на лепте записана слпво ))), то а процессе работы мешены появятся следующие конфпгурацпог ))) — начальная конфнгурацня (для краткостя здесь и далее а запнсн конфнгурапнн опускаем асс пустые снмзплы, расположенные левее первого непустого н прааее последнего не. пустогп); )))Π— следующая конфигурация; )))) — заключительная конфнгурацпя.
а Машина М, применима к любому слову в алфавите (О, )». Прнмср 1.39 (удвоение слова). Пострппм магпнпу с алфаен. том (О, (), кпторая по любому слпау в алфавите ()) строит даа аб таких слова; тоаансе, эта машина переводит конфигурацию вида ш в конфнгурацшо вида а 11 ... 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}
