Рекурсивная арифметика - Большая Энциклопедия Нефти и Газа, статья, страница 1
Если бы у треугольника был Бог, Он был бы треугольным. Законы Мерфи (еще...)

Рекурсивная арифметика

Cтраница 1


Рекурсивная арифметика на такой основе не развивается детально в той статье: это основная задача настоящей работы. Цель состоит в том, чтобы показать адекватность этой формулировки рекурсивной арифметики: конечный результат - это доказательство того, что рассматриваемая система эквивалентна системе Гильберта и Бернайса.  [1]

Рекурсивная арифметика, такая, какой она была введена в 2.1, непротиворечива в том смысле, что мы можем показать, что если р д, где р и q - определенные цифры, является доказуемым равенством, то р и q - одна и та же цифра.  [2]

Элементарными формулами рекурсивной арифметики являются равенства между термами, а класс всех формул строится из элементарных формул с помощью операций исчисления высказываний. Термами являются свободные цифровые переменные, знак 0 и знаки для функций.  [3]

В следующем далее изложении рекурсивной арифметики мы показываем, что логику и арифметику можно строить одновременно в исчислении равенств со свободными переменными, в котором единственными утверждениями являются равенства вида а bt где а и & означают функциональные выражения. С помощью этого исчисления равенств можно построить логику и арифметику с самого начала, с полной строгостью и со всеми деталями на значительно более элементарном уровне, чем было возможно до сих пор, и есть надежда, что первая половина этой книги окажется до Ступной первокурснику университета, специализирующемуся по математике.  [4]

Гедель показал, что средств рекурсивной арифметики вполне достаточно для математического построения такой модели и для ее формализации. Используемый им метод арифметизации состоит в арифметическом имитировании линейного расположения знаков в формулах формализованной математики. Действительно, логическую и математическую символику мы всегда можем выбрать таким образом, чтобы расположение символов и переменных в формулах было строго линейным.  [5]

Этот терм не является термом рекурсивной арифметики. Но для этого надо было бы указать какую-нибудь оценку для i; однако получение такой оценки в данном случае себя не оправдывает.  [6]

Логический формализм, лежащий в основе рекурсивной арифметики, представляет собой элементарное исчисление со свободными переменными. К нему в качестве исходных формул добавляются аксиомы равенства и формула О Ф О, а в качестве схем - схема индукции и схема примитивной рекурсии. Средств этого формализма уже достаточно для того, чтобы с их помощью можно было изобразить различные понятия, утверждения и доказательства элементарной арифметики. С другой стороны, этот формализм еще допускает определенное финитное истолкование. Но и без прямого обращения к этому истолкованию мы легко смогли доказать непротиворечивость этого формализма и даже установить, что всякая выводимая в нем формула, не содержащая формульных переменных, при любой замене входящих в нее свободных индивидных переменных цифрами после вычисления значений соответствующих функций переходит в истинную формулу.  [7]

Формализм F содержит термы и формулы рекурсивной арифметики), не считая, быть может, тех, в которых содержатся формульные переменные.  [8]

Среди прочего, он должен знать примитивно рекурсивную арифметику.  [9]

Таким образом, теперь мы уже выразили на языке рекурсивной арифметики все глаьные понятия, необходимые для определения вывода.  [10]

Любое вычисление значения рекурсивного терма без переменных в рамках рекурсивной арифметики может быть формализовано выводом равенства, указывающего результат этого вычисления. В этом выводе в качестве исходных формул используются рекурсивные равенства для рекурсивных функций, прямо или косвенно фигурирующих в этом терме, и аксиомы равенства. При этом использование этих формул производится с помощью подстановок и схем заключения.  [11]

В самой теории алгоритмов можно выделить исследования в области рекурсивной арифметики, куда входят различные классификации рекурсивных и рекурсивно перечислимых множеств) степени неразрешимости рекурсивно перечислимых множеств, исследования сложности записи алгоритмов и сложности алгоритмич. Обширным развивающимся разделом теории алгоритмов является теория нумераций.  [12]

В самой теории алгоритмов можно выделить исследования в области рекурсивной арифметики, куда входят различные классификации рекурсивных и рекурсивно-перечислимых множеств, степени неразрешимости ре-курсивно-перечислимых множеств, исследования сложности записи алгоритмов и сложности алгоритмич.  [13]

Тем самым мы попадаем в сферу действия того арифметического формализма, который получается из рекурсивной арифметики в результате присоединения исчисления предикатов ( в полном объеме), а также распространения на расширенную область формул схемы индукции и добавления ц-символа с относящимися к нему формулами ( iij), ( ц2) и ( мз) 2) - Этот формализм равносилен рассмотренному в гл.  [14]

Третьей системой, которая была развита для того, чтобы избавиться от рефлексивного парадокса, была рекурсивная арифметика Скодема.  [15]



Страницы:      1    2    3    4