Cтраница 2
Какой набор простейших функций и элементарных операций используется в теории рекурсивных функций. [16]
Книга является самой обширной из имеющихся монографий по математической логике и теории рекурсивных функций Она не предполагает со стороны читателя никаких специальных познаний и поэтому может считаться общедоступной. Книга предназначена для глубокого изучения предмета и рассчитана как на специалистов по математической логике и теории рекурсивных функций, так и на лиц, желающих впервые, но серьезно, изучить эти науки. [17]
Майхилл развивает в своем докладе абстрактную теорию самовоспроизведения автоматов, применяя теорию рекурсивных функций. Он приводит доказательства ряда теорем и дает содержательную интерпретацию формальных построений. [18]
Раздел 6.3 о логических ограничениях машин является кратким введением в теорию вычислимости, или теорию рекурсивных функций, основания которой были заложены в тридцатых годах такими логиками, как Пост, Тьюринг, Черч и Клини. [19]
КОНСТРУКТИВНЫХ МОДЕЛЕЙ ТЕОРИЯ - один из разделов математики, возникший на границе моделей теории, алгебры и теории рекурсивных функций и связанный с изучением вопросов эффективности в моделях и алгебрах. [20]
Книга адресована прежде всего студентам и аспирантам математических факультетов, желающим войти в круг идей и методов, которые существуют в данном разделе теории рекурсивных функций. Она также может быть полезна преподавателям вузов и научным сотрудникам, интересующимся вопросами классификации рекурсивных функций. [21]
Теоремы и правила, необходимые для составления алгоритмов преобразования ( переработки) операторных формул сборочных машин, строятся на базе методов математической логики, теории рекурсивных функций и теории алгоритмов. [22]
Этот результат показывает, что мы можем определить расположение наших относительных множеств на каждой степени арифметической иерархии, и поэтому они являются эквивалентными тем относительным множествам, которые используются в теории рекурсивных функций. Отсюда следуют все хорошо известные результаты, такие, например, как теорема о иерархии для Ап и Rn. [23]
Существование примитивно-рекурсивного частичного вычислителя, строящего для любой ( т - - п) - местной вычислимой функции ее вычислимую проекцию на первые т ее аргументов, является фундаментальной теоремой в теории рекурсивных функций ( так наз. Понятие трансляции с одного языка программирования на другой непосредственно связано с частичными вычислениями. [24]
В теории рекурсивных функций особо важное значение имеют три операции: суперпозиции, примитивной рекурсии и наименьшего корня. Рассмотрим каждую из них. [25]
Аналогичные теоремы могут быть получены и для Тьюринга машин. В теории рекурсивных функций наибольшее употребление нашли их сочетания, доставляемые оператором подстановки, оператором примитивной рекурсии и и-оператором. [26]
Имеется перевод: Роджерс Х Теория рекурсивных функций и эффективная вычислимость. [27]
Мы изложим наиболее простое и красивое доказательство теоремы Соловея, найденное Мартином. Это доказательство использует некоторые понятия теории рекурсивных функций. [28]
Лисп представляет собой язык так называемого функционального программирования. Он основан на алгебре списочных структур, лямбда-исчислении и теории рекурсивных функций. [29]
А выяснять, выводима ли А в этой теории или нет. Известно, что всякая формальная теория, содержащая нек-рый фрагмент теории рекурсивных функций, необходимо неразрешима. Отсюда следует неразрешимость элементарной арифметики, системы Цермело - Френкеля и многих других теорий. Примерами могут служить элементарная теория групп, теория двух отношений эквивалентности, элементарная теория частичного порядка. С другой стороны, имеются примеры интересных разрешимых теорий, таких, как элементарная геометрия, элементарная теория действительных чисел, теория множеств натуральных чисел с единственной операцией следования. Разрешимость теорий доказывается теоретико-модельными и синтаксич. Синтаксические методы часто дают более простые разрешающие алгоритмы. Так, например, для элементарной теории р-адических чисел разрешимость была установлена сначала теоретико-модельными методами. Позднее был найден примитивно-рекурсивный алгоритм распознавания выводимости для этой теории с помощью нек-рой модификации синтаксич. Существенной является оценка сложности алгоритмов разрешения теорий. Как правило, для разрешимых теорий имеется примитивно-рекурсивный разрешающий алгоритм, и проблема состоит в том, чтобы указать более точные границы сложности. Перспективным направлением исследований является изучение разрешимости естественных фрагментов известных формальных теорий. В этом отношении особенно подробно изучено классич. [30]