Высокая (вычислимость)
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В теории вычислимости степень Тьюринга [ X ] является высокой, если она вычислима в 0 ′ , а скачок Тьюринга [ X ′ ] равен 0 ′ ′ , что является максимально возможной степенью с точки зрения сводимости по Тьюрингу для скачка множества. которое вычислимо в 0 ′ . [1]
Аналогично, степень является высокой n, если ее n-й прыжок является (n+1)-м прыжком 0. В более общем смысле, степень d является обобщенно высокой n, если ее n-й прыжок является n-м прыжком соединение d с 0 ′ .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Соаре, Род-Айленд (1987). Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо порожденных множеств . Берлин: Springer-Verlag. п. 71. ИСБН 3-540-15299-7 .
 | Эта математической логике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |