ТАБЛИЧНАЯ СВОДИМОСТЬ
tt-сводимост ь,- специальный видалгоритмической сводимости.Пусть АиВ -два подмножества натурального ряда. Говорят, что Атаблично сводится к В (обозначение: если существует алгоритмf,к-рый по всякому натуральному числу астроит булеву функцию (функция задается, напр., своей таблицей, число аргументов функции может зависеть от а) и числа b1, .. .,bптакие, что принадлежность а к B эквивалентна истинности
Отношение является предпорядком на множестве всех подмножеств натурального ряда, упорядочение по нему образует верхнюю полурешетку. Отношению соответствует отношение эквивалентности на подмножествах натурального ряда, а именно: если и Классы эквивалентности по этому отношении) наз. табличными степенями (илиtt-степенями).
В теории алгоритмов рассматриваются также специальные виды Т. с., напр., ограниченная Т. с. (btt-сводимость), определяемая дополнительным требованием, чтобы число аргументов функции не зависело ота.Если в качестве функции j берется просто функция x1,то сводимость наз. т-сводимостью (обозначение: Сводимости, промежуточные междуtt-сводимостью и т-сводимостью (т. е. такие алгоритмич. сводимости что в частности все упомянутые выше, иногдааз. сводимостями табличного типа.
Лит.:[1] Роджерc X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [2] Дегтeв А. Н., лУспехи матем. наук