-1

Докажите, что существует вычислимая в обе стороны биекция между множеством простых чисел и {0, 1}∗.

задан 13 Фев 0:48

Для каждого двоичного слова u рассмотрим слово 1u. Это запись некоторого числа n в двоичной системе. По записи легко найти n; по n легко найти запись. Получается вычислимая в обе стороны биекция между множеством натуральных чисел и множеством двоичных слов.

Пусть p(n) означает n-е простое число. Его мы умеем находить при помощи алгоритма (например, решета Эрастосфена). Обратно, зная простого число p, мы этим же методом можем найти его номер n, для которого p=p(n). Это вычислимая в обе стороны биекция между множеством простых чисел и N. Остаётся взять композицию двух биекций.

(13 Фев 1:22) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×519
×454
×20

задан
13 Фев 0:48

показан
131 раз

обновлен
13 Фев 1:22

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

по почте:

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

по RSS:

Ответы

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

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