В.А. Успенский - Программа экзамена по дискретной математике (1107941), страница 3
Текст из файла (страница 3)
Общее определение универсальной функции с данным индексным множеством. Существование универсальных функций с произвольнымсловарном пространством в качестве индексного множества.Построение для данной универсальной функции, точки, в которой она не определена. Существование вычислимой функции, не продолжаемой до тотальной вычислимой функции. Главные универсальные функции.Главность универсальной функции Тьюринга.2.9. Нерешимые алгоритмические проблемыСуществование неразрешимого перечислимого множества в произвольном словарном пространстве.Теорема о нераспознавании свойств вычислимых функций по их индексам в произвольной главной универсальной функции. Нераспознаваемость свойств вычислимых функций по их программам.
Несуществованиеалгоритма, который по программе любой вычислимой тотальной функции распознаёт, совпадает ли эта функцияс заранее заданной вычислимой тотальной функцией f .Примеры нерешимых алгоритмических проблем из теории чисел и алгебры (без доказательства): из теориичисел — десятая проблема Гильберта; из алгебры — проблема представимости матриц.2.10. Ограниченность доказательной возможности формальной арифметикиУточнение неформального понятия «система доказательств» в терминах алфавита доказательств, множествадоказательств и функции выделения доказанного. Понятие дедуктики. Теорема Гёделя о неполноте.Неразрешимость формальной арифметики.Последняя компиляция: 28 октября 2005 г.Обновления документа — на сайте http://dmvn.mexmat.net.Об опечатках и неточностях пишите на dmvn@mccme.ru.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
