|
"
0
C
F
G
H
K
L
N
P
S
T
W
Z
А
Б
В
Г
Д
Е
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Э
Ю
Я
ТАБЛИЧНАЯ СВОДИМОСТЬЗначение ТАБЛИЧНАЯ СВОДИМОСТЬ в математической энциклопедии: tt- сводимост ь,- специальный вид алгоритмической сводимости. Пусть Аи В - два подмножества натурального ряда. Говорят, что Атаблично сводится к В (обозначение: Лит.:[1] Роджерc X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [2] Дегтeв А. Н., лУспехи матем. наук
|
|
|
|
если существует алгоритм f, к-рый по всякому натуральному числу астроит булеву функцию 
(функция задается, напр., своей таблицей, число аргументов функции может зависеть от а) и числа b1, . . ., b п такие, что принадлежность а к B эквивалентна истинности 
является предпорядком на множестве всех подмножеств натурального ряда, упорядочение по нему образует верхнюю полурешетку. Отношению 
соответствует отношение эквивалентности 
на подмножествах натурального ряда, а именно:
если 
и 
Классы эквивалентности по этому отношении) наз. табличными степенями (или tt -степенями). 
не зависело от а. Если в качестве функции j берется просто функция x1, то сводимость наз. т-сводимостью (обозначение: 
Сводимости, промежуточные между tt -сводимостью и т-сводимостью (т. е. такие алгоритмич. сводимости 
что 
в частности все упомянутые выше, иногдааз. сводимостями табличного типа.