Универсальные вычислимые функции

[huagarr]

Докажите, что множество FN вычислимых функций из N в N с областью
определения N неперечислимо.
Используем диагональный метод и показываем, что если множество
FN можно перечислить, то можно построить такую вычислимую
функцию f : N → N, что f не принадлежит FN

Как диагональный метод связан с неперечислимостью?

[mihaild]

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

[huagarr]

mihaild в сообщении #1363886 писал(а):

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

Рассматриваем диагональ таблицы,где строки таблицы-нумерация значений 1 аргумента ,столбцы-значение второго аргумента. Затем изменяем последовательность на диагонали
во всех точках. Сначала меняем значения
там, где d определена , затем, пользуясь предположением,
меняем значения во всех точках, где d не определена.
Затем рассматриваем строку, в которой располагается получившаяся последовательность
значений функции.

[mihaild]

Неправильно. Что несложно видеть по тому, что вы нигде не пользовались тотальностью. А множество частично рекурсивных функций перечислимо.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- уберите разрывы строк там, где они не требуются (не разделяют отдельные абзацы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.