418
правок
Изменения
Нет описания правки
* рефлексивность: <tex> L \le_T L </tex>
* транзитивность: из <tex> L \le_T M </tex> и <tex> M \le_T N</tex> следует <tex> L \le_T N </tex>
* Очевидно, что \equiv_T --- отношение эквивалентности
== Т-степени ==
Обозначим за \mathcal{D}_T множество классов эквивалентности языков по отношению \equiv_T, это множество будет множеством Т-степеней (тьюринговых степеней)
Определение: Т-степенью языка L называется его класс эквивалентности по отношению \equiv_T, то есть \mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}.
На Т-степенях можно ввести частичный порядок: для d_1, d_2 \in \mathcal{D}_T, d_1 \le d_2, если для каких-то L \in d_1, M \in d_2: L \le_T M, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.
=== Свойства ===
* \mathrm{R} — минимальный элемент в частичном порядке на Т-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара Т-степеней d_1, d_2 \in \mathcal{D}_T имеет наименьшую верхнюю границу d_1 \lor d_2 \in \mathcal{D}_T.
=== Тьюринговый скачок ===
== Литература ==
