alt text

задан 10 Фев '15 21:24

изменен 10 Фев '15 21:41

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
0

Да, верно, причём даже для случая перечислимого множества $%S$%. Если оно пусто, то доказывать нечего. Если оно непусто, то существует перечисляющая рекурсивная функция $%f$% от одной переменной (то есть такая, что $%S=\{f(0),f(1),f(2),\ldots\}$%). Если у Вас принималось соглашение, что 0 не входит в множество натуральных чисел, то $%f(0)$% не надо здесь писать, но вообще-то удобнее считать, что он входит.

На каждом шаге с номером $%n$% берём натуральное число $%f(n)$%. Снова оговорка по поводу нуля: если $%f(n)=0$% для хотя бы одного $%n$%, то он делится на все простые, а множество простых чисел разрешимо, поэтому здесь доказывать нечего. Считая, что $%f(n)\ge1$%, делим его с остатком на все числа от $%2$% до $%f(n)$%. Этот процесс описывается в терминах примитивно-рекурсивных функций. Если $%f(n)$% делится на 2, то число 2 печатаем. Далее печатаем 3, если $%f(n)$% делится на 3. При делении на очередное число 4 сначала проверяем, простое ли оно. Это можно сделать или при помощи подпрограммы (свойство простоты разрешимо). И так далее. Таким образом, мы последовательно напечатаем все простые делители каждого из чисел вида $%f(n)$%, что даёт рекурсивное перечисление множества всех простых делителей чисел из $%S$%.

ссылка

отвечен 11 Фев '15 0:27

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

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

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

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

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

отмечен:

×1,015
×479

задан
10 Фев '15 21:24

показан
557 раз

обновлен
11 Фев '15 0:27

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

по почте:

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

по RSS:

Ответы

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

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