Cтраница 3
Формальная теория называется разрешимой, если существует алгоритм, позволяющий по произвольной формуле А выяснять, выводима ли А в этой теории или нет. Известно, что всякая формальная теория, содержащая некоторый фрагмент теории рекурсивных функций, необходимо неразрешима. Отсюда следует неразрешимость элементарной арифметики, системы Цермело-Френкеля и многих других теорий. В теории доказательств разработаны тонкие методы интерпретации одних теорий в других; с помощью таких интерпретаций можно установить неразрешимость и ряда очень простых исчислений, в которых не интерпретируются непосредственно рекурсивные вычисления. Примерами могут служить элементарная теория групп, теория двух отношений эквивалентности, элементарная теория частичного порядка. С другой стороны, имеются примеры интересных разрешимых теорий, таких как элементарная геометрия, элементарная теория действительных чисел, теория множеств натуральных чисел с единственной операцией следования. [31]
Брауэра, а затем аналог континуума в конструктивном анализе, описываемый средствами теории рекурсивных функций ( см., например, Р. Л. Гуд-стейн, 1970) или теории нормальных алгорифмов ( школа А. А. Маркова и Н. А. Шанина; конструктивный математический анализ в этом стиле изложен в книге: Б. А. Куш-нер, 1973); конструктивный континуум с позиций классической ( неинтуиционистской и неконструктивистской) математики оказывается при этом не совсем континуумом - уже потому, что он счетен. [32]
В настоящее время имеется довольно много классов элементарных функций. Некоторые из них определены 40 - 50 лет назад и заняли прочное положение в теории рекурсивных функций. Все эти классы имеют индуктивные определения и замкнуты относительно операции суперпозиции и некоторых других эффективных операций. В предлагаемой читателю книге изучаются следующие классы элементарных функций: класс функций, элементарных по Сколему, класс функций, элементарных по Кальмару, начальные классы иерархии Гжегорчика и классы, обобщающие классы Гжегорчика. Кроме того, подробно исследован класс ограниченно арифметических предикатов, который представляет собой фундамент для большинства классов элементарных функций. [33]
Книга является самой обширной из имеющихся монографий по математической логике и теории рекурсивных функций Она не предполагает со стороны читателя никаких специальных познаний и поэтому может считаться общедоступной. Книга предназначена для глубокого изучения предмета и рассчитана как на специалистов по математической логике и теории рекурсивных функций, так и на лиц, желающих впервые, но серьезно, изучить эти науки. [34]
Элементарная теория чисел с такой точки зрения состоит из всех теорем, которые можно вывести из аксиом Пеано, самым сильным средством в которой является аксиома индукции. В такой формулировке она приобретает математический вкус и долго развивается как часть математической логики - теория рекурсивных функций. С доказательством замечательной теоремы Матиясевича в ней выделился законченныый теоретико-числовой фрагмент - теория диофантовых множеств, - который достоин завершать любой курс элементарной теории чисел. [35]
Работа [13] дает частичное описание модели, являющейся по своим характеристикам промежуточной между кинематической и сотообразной моделями фон Неймана. Исходя из нескольких аксиом для описания поведения машин, способных произвести другие машины, и на основании теории рекурсивных функций в работе [14] дано доказательство того, что машины могут создавать свои улучшенные варианты, но улучшение здесь понимается как способность отпечатывать более широкий класс истинных теорем, поэтому работа представляет больший интерес для логика, чем для биолога. [36]
Тогда парадокс будет уже представлять собой число, выраженное само через себя и содержащее внутреннее противоречие. Однако, пользуясь методами теории рекурсивных функций, можно дать новое определение числа, которое ни в коей мере не связано с парадоксом, ибо теория рекурсивных функций не признает существования числа в явном виде. Вместо числа вводится процесс, при помощи которого последовательно перебирается целый класс чисел, одним из экземпляров которого и является наше число. Таким образом, по сути дела ( трудность словесного пояснения этого вопроса очевидна), предусматривается обоснованная процедура, которая обеспечивает нам то, что мы просто натыкаемся на нужное число, а не провозглашаем его существования. Такой динамический, операционный подход полностью выдержан в духе кибернетики. Логику машины можно рассматривать как семантический континуум, и в ней попросту отсутствуют фиксированные детерминированные классы, принадлежащие или не принадлежащие самим себе. [37]
Теория чисел среди математических дисциплин выделяется скорее психологической установкой, чем предметом целые числа. Более сильное утверждение было бы неверным: в теоретико-числовых работах исследуются и алгебраические, и трансцендентные числа; или, вообще, не числа, а скажем, аналитические функции очень специального вида ( ряды Дирихле, модулярные формы); или геометрические объекты ( решетки, схемы над Z), Принадлежность результатов статьи к теории чисел определяется принятой автором системой ценностей: если арифметика в нее ие входит, то и статья не теоретико-числовая, хотя бы в ней шла речь исключительно о сравнениях и классах вычетов; если же входит, то что угодно - динамические системы или теория гомотопий - может оказаться мощным теоретико-числовым инструментом. Только по этой причине комбинаторика и теория рекурсивных функций обычно не считаются теоретико-числовыми дисциплинами, а теория модулярных форм считается. [38]
Требование, чтобы функция п натуральных аргументов была определена для каждого набора из п натуральных чисел, оказывается часто слишком обременительным ограничением. В 1938 С. К. Клини ввел понятие частично - рекурсивной функции ( ЧРФ) - функции, определенной не для всех натуральных значений аргументов, а лишь на нек-рых подмножествах натурального ряда, а в остальном удовлетворяющей определению ОРФ. Клини доказал также одну из важнейших теорем теории рекурсивных функций - теорему о нормальной форме для ОРФ ( и ЧРФ), позволившую существенно упростить первоначально очень громоздкие определения ОРФ и ЧРФ. [39]
Я родился в Калифорнии и приступил к работе в области математической логики, будучи студентом младших курсов в - Беркли в начале 1950 - х годов. Больше всего на меня повлияли, конечно, Альфред Тарский, его коллеги и студенты Калифор - - нийского университета. Наряду с другими предметами под руководством Рафаэля и Джулии Робинсон, которых я хочу поблагодарить за многие ценные идеи, я изучал теорию рекурсивных функций. [40]
Тогда парадокс будет уже представлять собой число, выраженное само через себя и содержащее внутреннее противоречие. Однако, пользуясь методами теории рекурсивных функций, можно дать новое определение числа, которое ни в коей мере не связано с парадоксом, ибо теория рекурсивных функций не признает существования числа в явном виде. Вместо числа вводится процесс, при помощи которого последовательно перебирается целый класс чисел, одним из экземпляров которого и является наше число. Таким образом, по сути дела ( трудность словесного пояснения этого вопроса очевидна), предусматривается обоснованная процедура, которая обеспечивает нам то, что мы просто натыкаемся на нужное число, а не провозглашаем его существования. Такой динамический, операционный подход полностью выдержан в духе кибернетики. Логику машины можно рассматривать как семантический континуум, и в ней попросту отсутствуют фиксированные детерминированные классы, принадлежащие или не принадлежащие самим себе. [41]
Хотя даже при окончательном анализе упорядочивание по простоте должно проводиться для каждого случая отдельно, в практически интересных случаях обычно появляются некоторые закономерности. Зачастую для рекурсивно определенного набора правильно сформулированных выражений находятся естественные способы упорядочивания, основанные на длине выражений, их глубине, определенной по вхождениям связок или композиций, и аналогичных характеристиках. Иногда могут быть построены и более сложные иерархические структуры, основанные, например, на сложности вычисления функций, относительной легкости их упрощения и сходимости. В теории рекурсивных функций уже много известно об иерархиях, связанных с относительной неразрешимостью и выводимостью, однако трудно усмотреть эвристические приложения этих теорий. Если для вычислимых функций могут быть построены такие структуры, то это указывает на их несомненную ценность. [42]
Это было сделано в работах неск. Теории, построенные этими авторами - теория рекурсивных функций Клини, исчисления А-конверсии Черча, теория машин Тьюринга, теория финитных комбинаторных процессов Поста - оказались эквивалентными ДРУГ другу и привели по существу к одному и тому же уточнению понятия алгорифма. Новые уточнения этого понятия, также эквивалентные прежним, были построены рядом др. авторов. В наст, время продолжают публиковаться все новые и новые теории алгорифмов, эквивалентные прежним теориям. [43]
Глубина вложенности обращений системы к самой себе допускается сколь угодно большой. Существуют разнообразные формы задания и проявления рекурсии. В математике рекурсивные методы присутствуют практически во всех областях. Одно из классических математических определений алгоритма базируется на теории рекурсивных функций. Рекурсивные методы повсеместно используются в исследованиях по искусственному интеллекту, в программировании, в вычислительных алгоритмах и в задачах проектирования сложных систем. [44]
Читатели, знакомые с теорией рекурсивных функций, без труда увидят, что наши теоремы принадлежат этой теории и легко могут быть переведены на ее язык. Ввиду этого доказательства получают двоякое значение. С другой стороны, их можно рассматривать как указания, исходя из которых, можно теоремы, сформулированные на языке теории рекурсивных функций, доказать формально средствами этой теории. Такие формальные доказательства не приводятся, чтобы не отвлекать читателя от содержания работы. Однако возможность формализации ясна всякому, кто знаком с теорией рекурсивных функций. [45]