2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Универсальные вычислимые функции
Сообщение26.12.2018, 21:20 
Аватара пользователя
Попробуйте расписать доказательство подробнее, может быть станет понятнее, где там используется диагональный метод.

 
 
 
 Re: Универсальные вычислимые функции
Сообщение26.12.2018, 21:45 
mihaild в сообщении #1363886 писал(а):
Попробуйте расписать доказательство подробнее, может быть станет понятнее, где там используется диагональный метод.

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

 
 
 
 Re: Универсальные вычислимые функции
Сообщение26.12.2018, 21:48 
Аватара пользователя
Неправильно. Что несложно видеть по тому, что вы нигде не пользовались тотальностью. А множество частично рекурсивных функций перечислимо.

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

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

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group