Математическая энциклопедия - простое множество
Связанные словари
Простое множество
рекурсивно перечислимое множество натуральных чисел, дополнение к-рого есть иммунное множество. П. м. являются промежуточными в смысле так наз. m-сводимости (см. Рекурсивная теория множеств).между разрешимыми множествами и творческими (креативными) множествами последние являются наибольшими среди перечислимых множеств в смысле m-сводимости. Пусть Р - произвольное П. м., а Кпроизвольное креативное множество натуральных чисел (напр., множество гёделевых номеров теорем формальной арифметики). Тогда не существует общерекурсивной функции f(x), сводящей Кк Р, т, е. такой, что
Сводимость Р к К имеет место всегда, а к Р не сводится ни одно разрешимое множество.
Лит.:[1] Успенский В. А., Лекции о вычислимых функциях, М., 1960; [2] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [3] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972. С. Н. Артемов.
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 553 | |
2 | 480 | |
3 | 476 | |
4 | 470 | |
5 | 452 | |
6 | 437 | |
7 | 435 | |
8 | 431 | |
9 | 421 | |
10 | 421 | |
11 | 419 | |
12 | 411 | |
13 | 402 | |
14 | 373 | |
15 | 372 | |
16 | 370 | |
17 | 363 | |
18 | 361 | |
19 | 361 | |
20 | 360 |