Игошин Математическая логика и теория алгоритмов (1019110), страница 85
Текст из файла (страница 85)
Команда д«0 зацикливает программу, и в результате работы цикла параметр у будет понижаться до тех пор, пока не получится конфигураци . 01"04,0!"<" »>, которая в силу команды 4,0 -э <1„, <ОЛ перейдет конфигурацию 01 "<1„<00!в<" »'. Дополнительные команды д„,О » <?а, <О, А, В, О, В, Б-, А создают на ленте требуемую конфигурацию <?о01е<" »<, доказывал<. щую, что функция <Р(х, у) правильно вычислена на машине Тыо. ринга. П Следствие 33.14. Всякая примитивно рекурсивная функция ви. числима по Тьюрингу.
Доказательство. Утверждение следует(ввиду определение 33.4 примитивно рекурсивной функции) из вычислимости по Тьюрингу простейших функций и свойств сохранения такой вычислимости операторами суперпозиции (теорема 33.2) и примитивной рекурсии (теорема 33.13). П Функции Аккермана. Напомним, что мы поставили задачу охарактеризовать вычислимые (с помощью какого-либо алгоритма) функции. Учитывая тезис Тьюринга (см. я 32), под алгоритмом достаточно понимать машину Тьюринга.
После того как в предыдущем пункте было доказано, что всякая примитивно рекурсивная функция вычислима (по Тьюрингу), возникает обратный вопрос: исчерпывается ли класс вычислимых (по Тьюрингу) фУнк ций примитивно рекурсивными функциями, т.е. всякая ли вмчислимая (по Тьюрингу) функция будет непременно примитивно рекурсивной? Применив теоретико-множественное понятие о мощности, достаточно легко ответить отрицательно на более общий вопр~~ исчерпывается ли класс всех функций примитивно рекурсивнь' ми функциями, т.е. все ли функции являются примитивно рекур сивными? Теорема 33. 15.
Существуют функции, не являющиеся примитив но рекурсивными. Доказательство. В самом деле, нетрудно понять, что мне жество всех примитивно рекурсивных функций счетно. Это обь"с няется тем, что каждая примитивно рекурсивная функция име ест конечное описание, т.е. задается конечным словом в некотор оМ (фиксированном для всех функций) алфавите. Множество вс всеХ конечных слов счетно. Позтому и примитивно рекурсивных Фуи» 342 „- имеется не более, чем счетное множество. В то же время мновсех функций даже от одного аргумента из Ф в гу имеет „„сть континуума.
Тем более, континуально множество функ)ув Фотлюбого конечного числа аргументов. Таким обра- цяЙ из непременно существуют функции, не являющиеся примизом, тявн ~о рекурсивными. (3 Отрицательным будет также ответ и на более узкий вопрос, пост тавленный в предыдущем пункте: все ли вычислимые (а в силу „са Тьюринга — вычислимые по Тьюрингу) функции можно тези ? опи „„сать как примитивно рекурсивные. Чтобы это установить, обходимо привести пример вычислимой функции, не являю- шейся примитивно рекурсивной. Идея примера состоит в том, чтобы построить такую вычислимую функцию, которая обладала бы свойством, каким не обладает ни одна примитивно рекурсивяая функция. Таким свойством может служить скорость роста функции, Итак, необходимо указать такую вычислимую функцию, которая растет быстрее любой примитивно рекурсивной функции и поэтому примитивно рекурсивной не является. Пример 33.1б.
Искомая функция конструируется с помощью последовательности вычислимых функций, в которой каждая функция растет существенно быстрее предыдущей. Начнем с построения такой последовательности. Мы знаем, что произведение растет быстрее суммы, а степень — быстрее произведения.
Начнем построение последовательности именно с этих функций, введя для них единообразные обозначения: Рл(а, у) = а+ у; Р~(а, у) = а у; Рг(а, у) = аг. Эти функции связаны между собой следующими рекурсивны- ми соотношениями: р,(а, у+ 1) = а+ ау = Рд(а, Р,(а, у)), Р~(а, 1) = а; р(а, у+ 1) = а . а'= Рь(а, Рг(а У)) 'г(а 1)родолжим эту последовательность, положив по определению лля и = 2 3 Р„,~(а,О) =1, Р„„(а,1) =а, Р„„(а, у+1) = Р„(а, Р„„(а, у)). ции р (Первое из равенств (1) предназначено для того, чтобы функ- " Р (а, У) были всюду определены.) Эта схема имеет вид приивнои рекурсии, и, следовательно, все функции Р„(а, у) р им"тивно рекурсивны.
Растут они крайне быстро. Например, * 1) = а, Рг(а, 2) = Рг(а, а) = а', ... Значение Рг(а, lс+1) у 'ается в результате возведения числа а в степень а Й раз. 343 Зафиксируем теперь значение а = 2. Получим последователь ность функций от одного аргумента: Рь(2, у), Р,(2, у), ... Введе„, две новые функции: В(х, у) = Р„(2, у) (она перечисляет послед нюю последовательность) и А(х) = В(х, х). Первая из них называ, ется функцией Аккерманн, а вторая — диагональной функцией Ак, кермана.
Для функции В(х, у) на основании введенных выше обозначь. ний и соотношений (1) вытекают следующие равенства: В(О,у) = 2+у, В(х+1,0) = зя(х), В(х+ 1,у+1) = В(х, В(х+ 1, у)), (2) 344 которые позволяют вычислять значение функции В(х, у), а следовательно, и значения функции А(х). При этом в процессе вычисления значения функции В(х, у) в некоторой точке используются вычисленные ранее ее значения в неких предыдущих точкак Этим схема (2) похожа на схему примитивной рекурсии. Но примитивная рекурсия ведется по одному аргументу, а в схеме (2) рекурсия ведется сразу по двум аргументам (такая рекурсия называется двойной, двухкратной, или рекурсией второй ступени). Пря этом существенно усложняется характер упорядочения точек, а следовательно, и понятие предшествующей точки. Это упорядочение не предопределено заранее, как в схеме примитивной рекурсии, где число и всегда предшествует числу н+ 1, а выясняется в ходе вычислений и для каждой схемы (2), вообще говоря, различно.
Например, В(3, 3) = В(2, В(3, 2)), а так как В(3, 2) = = Рз(2, 2) = Рз(2, Рз(2, 1)) = Рз(2, 2) = 2 = 4, то вычислению В в точке (3, 3) по схеме (2) должно предшествовать вычисление В в точке (2, 4): В(3, 3) = В(2, 4) = Р(2, 4) = 24 = 16. Проверьте самостоятельно, что вычислению В в точке (3, 4) должно предшествовать вычисление в точке (2, 1б).
Итак, функция В(х, у), а вместе с ней и функция А(х) вычислимы (по схеме (2)), а значит, в силу гипотезы Тьюринга, вычислимы посредством подходящей машины Тьюринга. Возникает вопрос, можно ли их вычисление свести к вычислению по схеме примитивной рекурсии, т.е. будут ли эти функции примитивно рекурсивными. Именно такова ситуация с функцией Аккермана А(х). Идея доказательства того, что функция А(х) не является примитивно рекурсивной, состоит в доказательстве того, что функция А(х) растет быстрее, чем любая примитивно рекурсивная функция, и поэтому не может быть примитивно рекурсивной. Более точно, для любой примитивно рекурсивной функции г(х) от одного аргумента найдется такое п, что для любого х > п будет А(х) > Ях) (Это доказал Аккерман в !928 г.) Идея доказательства этого утверждения состоит в следующем.
Сначала доказываются два свойства функции В(х, у), которые ис„сльзуются в дальнейшем: В(х, у+ 1) > В(х, у) (х, у = 1, 2, ...); В(х + 1, у) > В(х, у + 1) (х > 1, у > 2). Затем вводится понятие В-мажорируемой функции. Функция )(хи ..., х„) называется В-мажорируемой, если (Зт а )У)(Ъхо ..., х„) [шах(хь ..., х„) > ! -ь — > у(хо ..., х„) < В(т, гпах(хп ..., х„))]. Доказывается, что все примитивно рекурсивные функции В-мажорируемы. (Сначала устанавливается В-мажорируемость простейяих функций О, Я(х), („"(х). Затем доказывается, что оператор суперпозиции, примененный к В-мажорируемым функциям, дает В-мажорируемую функцию.
Аналогичным свойством обладает и оператор примитивной рекурсии.) Наконец, рассмотрим произвольную примитивно рекурсивную функциюг(х). В силу предыдущего утверждения, для некоторого т и любого х > 2 имеемГ(х) < В(т, х). Но тогда А(т+ х) = В(т+ х, т+ х) > В(т, т+ х) >г(т+ х). (Предпоследнее неравенство получено исходя из двух свойств функции В(х, у), сформулированных вначале.) Это и означает, что А(х) > г(х), начиная по меньшей мере с х = т+ 2. Итак, функция Аккермана А(х) не может быть вычислена по схеме примитивной рекурсии, но может быть вычислена по более сложной схеме (2).
Следовательно, примитивно рекурсивные функции не исчерпывают класса всех вычислимых функций, а свойство функции быть примитивно рекурсивной не равносильно ее свойству быть вычислимой (в том числе по Тьюрингу). Это говоРит о том, что если мы не оставляем затеи породить из простейших функций все вычислимые функции, то мы должны ввести какие-то дополнительные средства (методы) порождения. Таким средством явится оператор минимизации. Оператор минимизации. Это — оператор наименьшего числа в определении 33.5. В более общем виде его можно определить как оператор, применяемый к произвольному (и+ 1)-местному предикату Р(хо ..., х„, у) и дающий в результате п-местную функцию 9(хь ..., х„). Значение д(аь ..., а„) этой функции на наборе аргументов а„..., а„равно наименьшему из таких чисел у, что высказывание Р(аь ..., а„, у) истинно.
Оно обозначается руР(а„..., а„, у). Если же Наименьшего среди таких чисел не существует, то значение функ"ии <р(хь ..., х„) на этом наборе а„..., а, не определено. (Это озна"ает, что оператор минимизации может породить частичную, т.е. "е всюду определенную функцию.) Таким образом, ср(хь ..., х„) = Рур(хь ..., х„, у). Оператор минимизации называется также операторам наименьшего числа, или ц-операторам. 345 Преликат Р(хь ..., х„, у) (заданный над Ф), к которому при. меняется оператор минимизации, может быть сконструирован и двух числовых функций следующим образом: »1;(хь ..., х„, у) =1,'(хи ..., х„, у)», или из одной: 7"(х,, ..., х„, у) = 0». Так что оператор минимизации можно рассматривать как оператор, за данный на множестве числовых функций и принимающий значе.
ния в нем же. В этом своем качестве оператор минимизации является удоб ным средством для построения обратных функций. Действитель но, функция 1'-'(х) = цу[Яу) = х] (наименьший утакой, что 1"(у) = х) является обратной лля функции 1(х). (Поэтому в применении х одноместным функциям оператор минимизации иногда называ ют оператором обращения.) Рассмотрим примеры действия оператора минимизации для получения обратных функций. Пример 33.17. Рассмотрим следующую функцию, получающуюся с помощью оператора минимизации: Ы(х, у) = рг[у+ г = х] = рг[гЯ(х, у, г), 1зз(х, у, г)) = 1~'(х, у, г)].
Вычислим, например, И(7, 2). Для этого нужно положить у = 2 и, придавая переменной г последовательно значения О, 1, 2, ..., каждый раз вычислять сумму у+ г. Как только она станет равной 7, то соответствующее значение г принять за значение 47, 2). Вычисляем: г=0,2+0=2~7; г=1,2+1=3е7; г = 2, 2+ 2 = 4 е 7; г=3,2+3=5,-~7; г = 4, 2+ 4 = 6 е 7; г=5,2+5=7. Таким образом, ~1(7, 2) = 5. Попытаемся вычислить по этому правилу 43, 4): г = О, 4+ 0 = 4 > 3; г = 1, 4+ 1 = 5 > 3; г = 2, 4+ 2 = 6 > 3; Видим, что данный процесс будет продолжаться бесконечно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
