Табличная Сводимость

Tt- сводимост ь,- специальный вид алгоритмической сводимости. Пусть Аи В - два подмножества натурального ряда. Говорят, что Атаблично сводится к В (обозначение. если существует алгоритм f, к-рый по всякому натуральному числу астроит булеву функцию (функция задается, напр., своей таблицей, число аргументов функции может зависеть от а) и числа b1, . ., b п такие, что принадлежность а к B эквивалентна истинности Отношение является предпорядком на множестве всех подмножеств натурального ряда, упорядочение по нему образует верхнюю полурешетку. Отношению соответствует отношение эквивалентности на подмножествах натурального ряда, а именно. Если и Классы эквивалентности по этому отношении) наз. Табличными степенями (или tt -степенями).

В теории алгоритмов рассматриваются также специальные виды Т. С., напр., ограниченная Т. С. (btt- сводимость), определяемая дополнительным требованием, чтобы число аргументов функции не зависело от а. Если в качестве функции j берется просто функция x1, то сводимость наз. Т-сводимостью (обозначение. Сводимости, промежуточные между tt -сводимостью и т-сводимостью (т. Е. Такие алгоритмич. Сводимости что в частности все упомянутые выше, иногдааз. Сводимостями табличного типа. Лит.:[1] Роджерc X., Теория рекурсивных функций и эффективная вычислимость, пер. С англ., М., 1972. [2] Дегтeв А. Н., лУспехи матем. Наук.