Доказать, что предикат P(x), истинный только лишь на простых числах, примитивно рекурсивный.

Можно считать, что примитивно-рекурсивными являются все необходимые для решения базовые функции (сложение, умножение, симметрическая разность, факториал, возведение в степень...), а также известным факты об ограниченной минимизации и следствии из них.

задан 22 Ноя '15 19:40

изменен 22 Ноя '15 20:55

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

(22 Ноя '15 19:52) falcao
10|600 символов нужно символов осталось
0

Я буду по ходу дела использовать некоторые функции, которые здесь не были названы, но они в принципе легко строятся. Если нужны будут дополнительные пояснения, я готов их дать.

Построим функцию d(x): количество натуральных делителей x (при x=0 считаем эту функцию равной нулю). Рассматриваем все числа t от 1 до x. Для каждого из них берём остаток rm(x,t) от деления x на t (эта функция должны быть ранее построена). Если остаток равен 0, то действуем функцией $%\overline{sg}$%, которая в нуле равна 1, а в остальных случаях равна 0. Получается, что за каждый делитель мы кладём единицу в "копилку", и тем самым подсчитываем число делителей. Получается $%d(x)=\sum\limits_{t=1}^x\overline{sg}(rm(x,t))$%.

Возможность суммирования примитивно-рекурсивных функций в примитивно-рекурсивных пределах должна быть к этому моменту обоснована.

Далее замечаем, что x простое тогда и только тогда, когда d(x)=2. Рассматриваем модуль разности (это сумма $%a\dot-b$% и $%b\dot-a$%), и применяем к нему $%\overline{sg}$%. Получается искомый предикат $%P(x)=\overline{sg}|d(x)-2|$%, равный 1 на всех простых числах, и равный 0 на всех остальных.

ссылка

отвечен 22 Ноя '15 21:08

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×273
×194
×79
×49

задан
22 Ноя '15 19:40

показан
1596 раз

обновлен
22 Ноя '15 21:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru