Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 39
Текст из файла (страница 39)
Эти фуннции называются фуикциямн Анкермана. Из соотношений (5.б) следует, что В(0, у) =2+у; В (х+ 1 ~ О) = зд х; (5. 7) В (х+ 1, у + ! ) = В (х, В (х+ 1, у)), ~ Эти соотношения позволчют вычислять значения функций В(х, у) и, следовательно, А(х), причем для вычисления функции в данной точке нужно обратитьса к значению функции в предшествующей точке— совсем как в схеме примитивной рекурсии. Однако здесь рекурсия ведется сразу по двум переменным (таная рекурсия называется двойной, 'двукратной, или рекурсией 2-й ступени), и это существенно усложняет харантер упорядочения точек, а следовательно, и понятие предшествования точек также усложняется.
Например, В(3, 3)=В(2, В(3, 2)), а так как В(3, 2) «фз(2, 2) =2'=4, то вычислению В в точке (3,3) по схеме (5.7) должно предшествовать вычисление В в точке (2, 4); читатель может убедиться, что вычислению В в точке (3,4) должно предшествовать вычисление в точке (2, 1б). Важно отметить, что это упорядочение не предопределено заранее, как в схеме примитивной рекурсии, где л всегда предшествует л+ 1, а выясняется а ходе вычислений и для каждой схемы вида (5.7), вообще говоря, различно, Поэтому схему двойной рекурсии (в отличие от рассмотренной ранее одновременной рекурсии) не всегда удается свести н схеме примитивной рекурсии.
Теорема 5тй функция Аккермана А(х) растет быстрее, чем любая примитивно-рекурсивная функция, и, следовательно, ие является примитивно-рекурсивной. Более точно, для любой одноместной примитивно-рекурсивной функции 1(х) найдется такое л, что для любого хжл А (х) >7(х). Ограничимся наброском доказательства, опустив некоторые вы. кладки. 1, Вначале доиазываются два свойства фуинции В(х, у)г В (х, у + 1) > В (х, у) (х, у = 1, 2 ... )1 (5.8) В(х+1, у) > В(х, у+1) (х > 1, у > 2). (5.0) 2, Назовем функцию 1(хь ...,х„) В-мажорируемой, если существует натуральное ш, такое, что дли любых хь ..., х„, удовлетворяющих усло- 101 вию шах(хь ..., х„) >1, Цхь ..., х,) <В(т, шах(хь, х„)).
Покажем, что все примитивно-рекурсивные функции В.мажорируемы; а) для простейших функций О, х+1, 1" их В-мажорируемость оче. вядна; б) рассыотрнм оператор суперпозиции Я", причем для простоты выкладок ограничимся случаем л= 1, и=2, т.е, функцией 1(х) = Ь(й~(х), дэ(х)). Пусть функции Ь, дь дэ В-мажорируемы с числами ты т«ь тю соответственно. Положим т=шах(глм ш«ь тю). Тогда по определению В-мажорируемости и свойствам (5,8), (5.9) Л(х, х,) < В(т, шах(хч ха)); я, (х) < В (т, х) < В (т+ 1, х); р«(х) < В (т, х) < В (т+ 1, х) и, следовательно, с учетом (5.7) и (5.9) (х) =5(я (х), да (х)) < В (т, шах (д, (х), я» (х))) < В (т, В(т+1, х) )= =В(и+1, х+1) В(зл+2, х), т. е.
((х) В-мажорируема; в) рассмотрим теперь оператор примитивной рекурсии, ограничив- шись для простоты схемой (5.3): ((О) = с,; 7(х+ 1) = Ь(х, ((х)). Пусть Ь В-мажорируема, т. е, Ь(хь х»)<В(тм шах(хь х»)) при пзах(хь х»)>1. Докажем индукцией по х, что 1 В-мажорируема. Учитывая условие в определении В-мажорируемости, индукцию на- до начинать с х=2.
Пусть ((2) =с». Из (5.8), (5.9) следует, что В(х+ +1, 2) >В(х, 2), поэтому найдется такая велвчииа ш», что В(т„2) > >с»=г(2). положим т=шах(ть лы)+1. Очевидно, что 1(2) <В(т, 2). Пусть теперь ((й) <В(ш, й). Тогда 7(я+1) = й(й, ((я)) > В(та, шах(х, ((л))). (5.10) Если глад(й, ((е)) =-л, то 7(й+1) <В(тм й) <В(т, а+1).
Если же гпах(й, 1(я))=)(й), то, используя (5.7) — (5.10) и то, что тамит — 1, имеем ((а+1) <В(тм г'(й)) <В(ты В(ги, «)) <В(т — 1, В(т, й))= =В(т, й+1), что и завершает индукцию. Из пп, «а» — «в» следует, что все примитивно-рекурсивные функции. В-мажорируемы. 3 Пусть 7(х) — примитивно-рекурсивная функция.
В силу п, 2 для некоторого т и хм2 1(х) <В(гл, х) . Но тогда А (т+ х) = В (т+ х, т+ х) > В (т, ел + х) > 7" (и + х), т.е. А(х)>1(х), начиная по крайней мере с х=лг+2. С) 192 Общерекурсивные и частично-рекурсивные функции. Функция Аккермана А(х) является примером вычислимой, но не примитивно-рекурсивной функции. Этот пример говорит о том, что средства построения вычнслимых функций нуждаются в расширении.
Операторы кратной рекурсии (т. е. по нескольким переменным одновременно) не дают желаемого замыкания класса всех вычислнмых функций: было показано, что для любого а найдется функция, определимая с помощью и-кратной рекурсии (п-рекурснвная), но не (а — 1)-рекурсивная. Более подходящим для атой цели оказывается неограниченный р-оператор (в дальнейшем прилагательное «неограниченный» будем опускать). Функция называется частично-рекурсивной, если она может быть построена из простейших функций О, х+1, 7" с помощью конечного числа применений суперпозиции, примитивной рекурсии н р-оператора. По определению р-оператор применяется к предикатам.
Поскольку в теории рекурсивных функций истинность пре' диката Р(х) всегда связана со справедливостью йекоторого равенства (например, 11р(х)= 11 и, наоборот, всякое равенство является предикатом от содержащихся в нем переменных, то ц-оператору можно придать стандартную форму, например ~(хь...,х,) =рд(д(хь...,х„ь у) =х„) или ~(хь... х«) =М(й'(хь-, х» у) =О).
Будучи применен к вычислимой функции, и-оператор снова дает вычислимую функцию (т. е. сохраняет вычислимость). Действительно, для вычисления функции 7 (хь ..,, х„) = ну(д(х„..., х, у) =О) на наборе хь ..., х, существует следующая простая процедура; вычисляем д на наборах (х„..., х„, О), (хо ..., х„, 1), ... до тех пор, пока не получим значение нуль. Однако в отличие от рассмотренных ранее процедур она может не привести к результату: это произойдет в случае, когда па данном наборе х„ ...,х, уравнение д(хь ..., х„ у) =0 не имеет решения. В таком слУчае фУнкциЯ 7(хь ..., х„) считаетсЯ неопРеДеленной, Например, обратная к х+1 функция х — 1=ру(у+1= =х) не определена при х=0.
Заметим, что механизм возникновения неопределенности здесь такой же, как и прн вычислениях на машине Тьюринга: в случае неопределенности процесс вычисления не останавливается. Таким образом, среди рекурсивных функций появляются не полностью определенные, т. е.
частичные функции; операторы над частичными функциями порождают новые частичные функции. Прн атом характер неопределенности может оказаться довольно сложным, а именно: для данно- 13-750 193 го набора значений хг, ...,х„не найдется способа установить, определена ли функция 1 на этом наборе, и нам придется продолжать процесс вычисления неопределенное время, не зная, остановится он или нет. В случае, когда функция д, к которой применяется 1а-оператор, сама является частичной, функция 1(хь ..., х,) = =ру(у(хь ..., х„у) =О) вычисляется с учетом следующего условия: если для у='О, 1, ..., 1 — 1 д(хг, ..., х„, у) ныл, а у(х„..., х„1) не определена, то и 1(хг, ..., х,) не определена. Например, функция 1(х) =ру(у — х=51 при х=1 не определена (хотя уравнение у — 1=5 имеет решение х=б), так как функция у — 1=5 не определена при у=О. (т1астично-рекурсивная функция называется оби(ерекурсивной, если она всюду определена.
Из сказанного ранее о неопределенности видно, что не всегда частично-рекурсивную функцию можно эффективным образом доопределить до общерекурсивной. Подробнее об этом — в следующем параграфе. Тезис Черча. Связь рекурсивных функций с машинами Тьюринга. Понятие частично-рекурсивной функции оказалось исчерпывающей формализацией понятия вычислимой функции. (В частности, функция Аккермана общерекурсивна; доказательство этого факта можно найти, например, в [381, задача 42,а), Это обстоятельство выражено в виде тезиса Черча, являющегося аналогом ' тезиса Тьюринга для рекурсивных функций: всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивна. Из сопоставления двух тезисов вытекает утверждение функция вычислила машиной Тьюринга тогда и только тогда, когда она частично-рекурсивна, 'Это утверждение об эквивалентности двух алгоритмических моделей является (в отличие от тезисов) вполне точным математическим утверждением и, следовательно, должно быть доказано.
Для доказательства разобьем его на две теоремы. Теорема 5.6. Всякая частично-рекурсивная функция вычислима на машине Тьюринга. План доказательства ясен: сначала доказывается, что простейшие функции вычислимы (это довольно очевидно), а затем — это операторы суперпозицпи, примитивной рекурсии и р-оператор сохраняют вычислимость. Ограничимся построением машины Тьюринга для опера. ' Исторически тезис Черча бмл сформулирован раньше тезиса Тью. ринга. 194 тора примитивной рекурсии Р., Для простоты обозначений рассмотрим случай в=1. Пусть 1(х, у) =Р~(й, л), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
