418
правок
Изменения
→Тьюринговый скачок
=== Тьюринговый скачок ===
Обозначим за H язык программ, останавливающихся на пустом входе. Обозначим за H^f язык программ, использующих f в качестве оракула и останавливающихся на пустом входе.
Можно показать, что:
* f <_T H^f
* Если f \le_T g, то H^f \le_T H^g
Тогда тьюринговым скачком Т-степени d называется Т-степень языка H^L, где L — произвольный язык в d. Заметим, что если L \equiv_T M, то H^L \equiv_T H^M, поэтому определение корректно. Оператор тьюрингова скачка обозначим как J : \mathcal{D}_T \to \mathcal{D}_T.
== Литература ==
