Изменения

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством Т<tex>T</tex>-степеней (тьюринговых степеней).

Т<tex>T</tex>-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.

На Т<tex>T</tex>-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т<tex>T</tex>-степени.

* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на Т<tex>T</tex>-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.* Любая пара Т<tex>T</tex>-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

Тогда тьюринговым скачком Т<tex>T</tex>-степени <tex>d</tex> называется Т<tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.