Игошин Математическая логика и теория алгоритмов (1019110), страница 83
Текст из файла (страница 83)
Для всякой ли функции можно указать вычисляющую ее машину Тьюринга? Если нет, то для каких функций существует вычисляющий их алгоритм (машииа Тьюринга), как описать такие, как говорят, алгоритмически или эффективно вычислимые функции? Исследование этих вопросов привело к созданию в 1930-х гг. теории рекурсивных функций. При этом класс вычислимых функций (названиых здесь рекурсивными) получил такое описание, которое весьма напомнило процесс построения аксиоматической теории на базе некоторой системы аксиом. Сначала были выбраиы простейшие функции, эффективная вычисляемость которых была очевидна (своего рода «аксиомы»).
Затем сформулированы некоторые правила (назваиные операторами), на основе которых можно строить новые функции из уже имеющихся (своего рода 333 «правила вывода»). Тогда требуемым классом функций будет совокупность всех функций, получающихся из простейших с помощью выбранных операторов. Наша цель будет состоять в том, чтобы доказать, что этот класс функций совпадет с классом функций, вычислимых с помощью машин Тьюринга. Идея доказательства этого утверждения в одну сторону проста; сначала доказать вычислимость по Тьюрингу простейших функций, а затем вычислимость по Тьюрингу функций, получающихся из вычислимых по Тьюрингу функций с помощью выбранных операторов.
Основные понятия теории рекурсивных функций и тезис Черча. Приступим к построению класса рекурсивных функций в соответствии с изложенными принципами. Напомним, что рассматриваются функции, заданные на множестве натуральных чисел и принимающие натуральные значения. Функции предполагается брать частичные, т.е. определенные, вообще говоря, не для всех значений аргументов.
В качестве исходных простейших функций выберем следующие: Ю(х) = х+ 1 (функция следования); 0(х) = О (нуль-функция); 1„"(хо хь ..., х„) = х„(функции-проекторы, 1 < т < и). Вычислимость (более того, правильная вычислимость) этих функций с помощью машины Тьюринга установлена в примерах 32.7 и 32.!О. Далее, в качестве операторов, с помощью которых будут строиться новые функции, выберем следующие три: операторы суперпозиции, примитивной рекурсии и минимизации. Определение 33.1 (оператор суперпозиции).
Будем говорить, что п-местная функция р получена из т-местной функции3 и и-местных функций «н ..., я с помощью оператора суперпозиции, если для всех хь ..., х„ справедливо равенство: д(хн ..., х„) = 3(д,(хь ..., х„), ..., я (хн ..., х„)). Понятие суперпозиции функций и сложной функции хорошо известно, но нас сейчас этот оператор интересует с точки зрения его взаимоотношений с процессом вычислимости функций с помощью машин Тьюринга. Теорелла 33.2. Если функции Т(хь ..., х ), д,(хь ..., х„), ..., я„(хь ..., х„) правильно вычислииы по Тьюрингу, то правильно вычислимо и сложная функция (суперпозиция функциЯ: <Р(хь ..., х„) = Яд,(хь ..., х„), ..., Я (хн ..., х„)).
Д оказ а тел ьство. Руководствуясь определением 32.9 композиции машин Тьюринга, нетрудно понять, что если машина Г правильно вычисляет функцию 3(у), а машина 6 правильно вы- 334 числяет функцию л(х), то композиция этих машин г" 6 правильно вычисляет суперпозицию этих функций 1(е(х)): <1)01"; 6: (1012<">; Г: д01 ')). Рассмотрим более сложную суперпозицию вычислимых функций: (р(х, у) =1(я)(х, у), лг(х, у)). Пусть машины Г, 6<, 6, правильно вычисляют функции 3, я„хг соответственно.
Сконструируем машину Тьюринга, правильно вычисляющую сложную функцию (р(х, у), пользуясь введенными в э 32 машинами сдвига, транс- позиции, копирования и нулевой функции: Сконструируйте самостоятельно композицию машин, правильно вычисляющих функцию <р(х, у) = Щ(х, у), яг(х, у), «3(х, у)). Подстановки указанного вида достаточно специфичны (все функции я имеют одно и то же число аргументов) и не исчерпывают всевозможных подстановок, которые можно производить над функциями. Но благодаря функциям-проекторам 1„" этот недостаток легко устраняется: любая суперпозиция функций в функции может быть выражена через суперпозиции указанного вида и функции-проекторы. В самом деле, например, суперпозиция Щ(х„хг), Хг(х!)) может быть в требуемом виде представлена так: Ял<(х), хг), 1! (хг(х!) Кз(х!))), где 83(х!) — любая функция от хь В свою очеРель, используя подстановку и функции-проекторы, можно переставлять аргументы в функции: ,< (хг, х), хзу ..., худ) У(12(х<у хг)р 1! (х)ф хг), хз " ~ ха)~ 1(х!з х)э хз~ "э хп) — 1(1! (Х)> х2) 1! (х!э хг)~ хз " х ).
Поэтому можно считать, что теорема полностью доказана. П Овределевие 33.3. Говорят, что (и+ 1)-местная функция <р получена из л-местной функции 1"и (и+ 2)-местной функции лс помо<цью оператора пршиитиввой рекурсии, если для любых х„..., х„, у справедливы равенства: <р(х„..., х„, 0) = 1(х<, ..., х )' (р(х„..., х„, у+ 1) = я(х), ..., х„, у, <р (х! " х. У)) 335 1~2. 6)! Ц: бг. Б-: г": (1О 3 ф)0: д 01.01 01"О! дО1.ОР; 01"01»<10!а<" »); 0!а<" »<101"О!»; 0!а<к')д01пй»); ,10!а<к'»)0!а<' »; д01»(а(», », 2,(к»)).
Ч!)О 1д(а' <ь). Пара этих равенств называется схемой примитивной рекурсии. 3десь важно отметить то, что, независимо от числа аргументов в у, рекурсия ведется только по одной переменной у; остальные п переменных хн ..., х„на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров. Кроме того, схема примитивной рекурсии выражает каждое значение определяемой функции д не только через данные функции 3 и я, но и через так называемые предыдущие значения определяемой функции ях прежде чем получить значение <р(хн ..., х„, й), придется проделать й+ 1 вычисление по указанной схеме — для у = О, 1, ..., й, Определение 33.4.
Функция называется примитивно рекурсивной, если она может быть получена из простейших функций О, 5, 1„" с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Наконец, введем заключительный, третий, оператор. Определение 33.5 (оператор минимизации). Будем говорить, что и-местная функция у получается из (и+ 1)-местных функцийЯ, и32 с помощью оператора минимизации, или оператора наименьшего числа, если для любых хн ..., х„, у равенство <р (хн ...,х„) = у выполнено тогда и только тогда, когда значения Яхн ..., х„, О), ..., 3;(хь ..., х„, у — 1) (1 = 1, 2) определены и попарно неравны: );(хь ..., х„, О) ~ Яхн ..., х„, О), ..., У;(хн ..., х„, у-1) ~ Я~(хн ..., х„, у-1), а Я,(хь ..., х„, у) = 6(хн ..., х„, у). Коротко говоря, величина у(хь ..., х„) равна наименьшему значению аргумента у, при котором выполняется последнее равенство.
Используется следующее обозначение: <р(хн ..., х„) = )ту[),(хь ..., х„, у) = );(хн ..., х„, у)]. В частном случае может быть |~ = О. Тогда ср(хн ..., х„) = )ту[У(хн ..., х„, у) = О]. Оператор минимизации называется также р-оператором. Этот оператор предназначен для порождения следующего важного класса рекурсивных функций. Определение 33.6. Функция называется частично рекурсивной, если она может быть получена из простейших функций О, 5,!" с помощью конечного числа применений суперпозиции, примитивной рекурсии и )г-оператора. Если функция всюду определена и частично рекурсивна, то она называется ойщерекурсивной. (Отметим, что не всегда частично рекурсивную функцию можно эффективно доопределить до общерекурсивной.) Ясно, что всякая примитивно рекурсивная функция будет и частично рекурсивной (и даже общерекурсивной, так как каждая примитивно рекурсивная функция всюду определена), посколькУ для построения частично рекурсивных функций из простейших 336 используется больше средств, чем для построения примитивно рекурсивных функций.
В то же время класс частично рекурсивных функций шире класса примитивно рекурсивных функций„так как все примитивно рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются и функции не всюду определенные. Понятие частично рекурсивной функции оказалось исчерпывающей формализацией понятия вычислимой функции. При построении аксиоматической теории высказываний (см. гл. П1) исходные формулы (аксиомы) и правила вывода выбирались так, чтобы полученные в теории формулы исчерпали бы все тавтологии алгебры высказываний. К чему же стремимся мы в теории рекурсивных функций, почему именно так выбрали простейшие функции и операторы для получения новых функций? Рекурсивными функциями мы стремимся исчерпать все мыслимые функции, поддающиеся вычислению с помощью какой-нибудь определенной процедуры механического характера. Подобно тезису Тьюринга, в теории рекурсивных функций выдвигается соответствующая естественно-научная гипотеза, носящая название тезиса Черна: Числовая функция тогда и только тогда алгоритмически (или машинно) вычислила, когда она частично рекурсивна.
И эта гипотеза не может быть доказана строго математически, она подтверждается практикой, опытом, ибо призвана увязать практику и теорию. Все рассматривавшиеся в математике конкретные функции, признаваемые вычислимыми в интуитивном смысле, оказывались частично рекурсивными. Теперь мы рассмотрим более подробно классы примитивно рекурсивных функций и частично рекурсивных функций и докажем, что все функции из каждого из этих классов вычислимы на подходящих машинах Тьюринга. Примитивно рекурсивные функции. Итак, функция примитивно рекурсивна, если она может быть получена из простейших функций О, 5, 7" с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
