Математическая энциклопедия - табличная сводимость
Связанные словари
Табличная сводимость
Отношение является предпорядком на множестве всех подмножеств натурального ряда, упорядочение по нему образует верхнюю полурешетку. Отношению соответствует отношение эквивалентности на подмножествах натурального ряда, а именно: если и Классы эквивалентности по этому отношении) наз. табличными степенями (или tt -степенями).
В теории алгоритмов рассматриваются также специальные виды Т. с., напр., ограниченная Т. с. (btt- сводимость), определяемая дополнительным требованием, чтобы число аргументов функции не зависело от а. Если в качестве функции j берется просто функция x1, то сводимость наз. т-сводимостью (обозначение: Сводимости, промежуточные между tt -сводимостью и т-сводимостью (т. е. такие алгоритмич. сводимости что в частности все упомянутые выше, иногдааз. сводимостями табличного типа.
Лит.:[1] Роджерc X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [2] Дегтeв А. Н., лУспехи матем. наук
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985
Вопрос-ответ:
Самые популярные термины
1 | 548 | |
2 | 474 | |
3 | 471 | |
4 | 464 | |
5 | 448 | |
6 | 431 | |
7 | 430 | |
8 | 425 | |
9 | 417 | |
10 | 416 | |
11 | 414 | |
12 | 405 | |
13 | 397 | |
14 | 370 | |
15 | 367 | |
16 | 362 | |
17 | 357 | |
18 | 356 | |
19 | 356 | |
20 | 355 |