Cтраница 1
Гжегорчик [6] и Крипке [2] предложили интересную философскую интерпретацию понятия истинности в интуиционистских структурах Бета и Крипке, которая может служить хорошим эвристическим средством отыскания новых математических фактов и проливает свет на значение теории интуиционистских моделей. Эта интерпретация может быть модифицирована и по отношению к рассматриваемым структурам. [1]
Гжегорчик [3] показал, что класс cfj замкнут относительно явных преобразований, булевых операций и ограниченной квантификации, а Смульян [ 8, стр. [2]
Идею, заложенную в определении классов Гжегорчика, можно легко обобщить в различных направлениях. [3]
Нетрудно проверить ( классически), что формула Гжегорчика истинна во всякой модели Крипке с постоянной областью. [4]
Такая граница для функции, определенной при помощи примитивной рекурсии, была введена еще Гжегорчиком [3] в понятии ограниченной рекурсии. [5]
Представляют интерес некоторые проблемы, связанные с двойной рекурсией ( проблемы 6 и 9 статьи Гжегорчика, стр. [6]
При этом выберем /, К и L достаточно простыми из 2; см. например, статью Гжегорчика в настоящем сборнике, стр. [7]
Рекурсивные равенства, определяющие работу / - ограниченных машин, приводят естественным образом к получению классов Ег с помощью совместной итерации, с другой стороны, ограниченная рекурсия играет решающую роль в порождении классов ( эг Гжегорчика. [8]
Для любых положительных целых i и k если h e Fit / е Fh и g е Fi h, тогда f е / % &, где f определяется из g, h и j посредством ограниченной рекурсии. Следуя Гжегорчику, говорим, что f определяется из g, h и j при помощи ограниченной рекурсии. [9]
Один способ классификации рекурсивных функций восходит к истокам теории алгоритмов и связан с порождением тех или иных классов рекурсивных функций из множеств ( обычно конечных) достаточно простых исходных функций посредством различных вычислимых операций. Так строятся классификации Петер, Гжегорчика, Акста, Клини. При этом обычно возникает растущая иерархия ( цепочка) классов по некоторому трансфинитному типу. [10]
Это обстоятельство, быть может, впервые проявилось в работе Аккермана ( 1927 г.), где была построена вычислимая функция, мажорирующая любую примитивно рекурсивную функцию и носящая имя автора. С тех пор на протяжении 40 лет основанные на скорости роста соображения неоднократно встречались во многих работах ( например, в работах Гжегорчика ( 1953 г.), Б. А. Трахтенброта [5] ( 1956 г.), Ричи ( 1962 - 1963 гг.), В. А. Козмидиади и С. С. Марченкова ( 1965 - 1967 гг.), Я. Б. Казановича ( 1967 г.)), связанных с классификацией рекурсивных функций и вычислений. [11]
& г, ) ( г2) относительно fr ( x y), где fr ( x y) есть г-я функция Гжегорчика ( стр. [12]
Теорема об ш-полноте принадлежит Генкину и Оре. Позднее различными авторами были получены разнообразные ее усовершенствования. Одно из них - теорема об опускании типов 2.2.3, восходящая к Гжегорчику, Мостовскому, Рылль-Нардзев - скому. [13]
В настоящее время имеется довольно много классов элементарных функций. Некоторые из них определены 40 - 50 лет назад и заняли прочное положение в теории рекурсивных функций. Все эти классы имеют индуктивные определения и замкнуты относительно операции суперпозиции и некоторых других эффективных операций. В предлагаемой читателю книге изучаются следующие классы элементарных функций: класс функций, элементарных по Сколему, класс функций, элементарных по Кальмару, начальные классы иерархии Гжегорчика и классы, обобщающие классы Гжегорчика. Кроме того, подробно исследован класс ограниченно арифметических предикатов, который представляет собой фундамент для большинства классов элементарных функций. [14]
В настоящее время имеется довольно много классов элементарных функций. Некоторые из них определены 40 - 50 лет назад и заняли прочное положение в теории рекурсивных функций. Все эти классы имеют индуктивные определения и замкнуты относительно операции суперпозиции и некоторых других эффективных операций. В предлагаемой читателю книге изучаются следующие классы элементарных функций: класс функций, элементарных по Сколему, класс функций, элементарных по Кальмару, начальные классы иерархии Гжегорчика и классы, обобщающие классы Гжегорчика. Кроме того, подробно исследован класс ограниченно арифметических предикатов, который представляет собой фундамент для большинства классов элементарных функций. [15]