Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Петер Р.N. Рекурсивные функции
 
djvu / html
 

230 РЕКУРСИВНЫЕ ФУНКЦИИ
Все сказанное выше без затруднений переносится и на многоместные функции.
§ 23. ВОПРОС ОБЩЕЙ РАЗРЕШИМОСТИ АРИФМЕТИЧЕСКИХ ПРОБЛЕМ
1. Под «арифметическими» высказываниями мы будем понимать высказывания о равенстве двух теоретико-числовых полиномов. С формальной стороны мы имеем здесь дело с высказываниями, которые можно записать с помощью математических знаков «+», « • », « — » и логических знаков; при этом допускается употребление «знака всеобщности» (х) и «знака существования» (Ех) также и тогда, когда не указывается никаких границ для х.
Можно показать, что известные проблемы теории чисел, не решенные до сих пор, являются арифметическими в указанном смысле. Например, гипотезу Гольдбаха о том, что любое четное число, превосходящее 2, есть сумма двух простых чисел, можно следующим образом сформулировать в виде арифметического высказывания. Каждое четное число допускает запись х+х. Тот факт, что число г/>1 является простым, равносилен тому, что если число у представимо в виде произведения u-v, то оно равно либо и, либо v. Следовательно, утверждение, гласящее, что каждое число вида х-\-х равно некоторой сумме у+г, в которой как у, так и z являются простыми числами, с помощью знаков «+», «•», « = » можно записать в виде
& (и) (v) [z=«-a— -(z
(Эта формула содержит также утверждение, что указанные у и z существуют и для х—0 и х=1; действительно, значения у и z следует в первом случае принять равными 0, а во втором — равными 1.)
То, что арифметической является также проблема Ферма, уже далеко не очевидно. В ее формулировке участвуют степени с переменными показателями, и не так-то легко представить себе, что их можно выразить посредством только сложений и умножений.
Однако, как показал Гёдель, все примитивно-рекурсивные отношения можно сформулировать в виде арифметических высказываний1).
дующий способ для эффективного распознавания, определяет ли число п обще-рекурсивиую функцию. К определяющим равенствам, задающим функции <\1 И
(х(т)=(Аа,[т(/г, m, w)=0], присоединим равенство
Выяснив, определяет ли полученная система равенств обще-рекурсивную функцию или нет, мы тем самым получим ответ и на интересующий нас вопрос для /г. — Прим. перке. Ч Гёдель [1], § 3.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 231 232 233 234 235 236 237 238 239 240 250 260


Математика