alt text

задан 18 Фев '15 11:01

изменен 18 Фев '15 15:13

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


9917

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

Рассмотрим случай, когда разрешимое множество бесконечно: $%A=\{a_1,a_2,\ldots,a_n,\ldots\}$%. Можно считать, что его элементы расположены в порядке возрастания. Тогда положим $%f(n)=a_n$%. Функция $%f$% вычислима при помощи такого алгоритма: рассматриваем число $%n$%, и начинаем последовательно проверять для чисел 0, 1, 2, ... , принадлежат ли они множеству $%A$%. Делаем так до тех пор, пока не получим $%n$%-й по счёту элемент, принадлежащий $%A$%. Это и будет $%a_n$%. Процесс продолжается конечное время, так как множество $%A$% бесконечно, и такой элемент рано или поздно обнаружится.

Если $%A$% конечно, то его элементы можно напечатать в порядке возрастания, и далее печатать наибольший из этих элементов, то есть $%f(k)=a_k$% при $%k\le n$% и $%f(k)=a_n$% при $%k > n$%.

Доказательство обратного утверждения, по сути, было разобрано здесь.

ссылка

отвечен 18 Фев '15 17:23

@falcao а что является обратным утверждением?

(28 Фев '17 9:56) tofikk

@tofikk: вопрос имеет форму "тогда и только тогда". В первой части было доказано утверждение p=>q. Обратное -- это импликация в обратную сторону: q=>p. В данном случае p есть высказывание "A разрешимо", а q есть "A является множеством значений неубывающей вычислимой функции".

Обращаю внимание на то, что ничего нового я здесь не сообщил. Всё это написано в тексте.

(28 Фев '17 10:24) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,037
×480

задан
18 Фев '15 11:01

показан
750 раз

обновлен
28 Фев '17 10:24

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

по почте:

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

по RSS:

Ответы

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

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