Изменения

* Очевидно, что <tex>\equiv_T --- </tex> — отношение эквивалентности

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

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

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

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

Обозначим за <tex>H </tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f </tex> язык программ, использующих <tex>f </tex> в качестве оракула и останавливающихся на пустом входе.

* <tex>f <_T H^f </tex> * Если <tex>f \le_T g</tex>, то <tex>H^f \le_T H^g</tex>

Тогда тьюринговым скачком Т-степени <tex>d </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>.