WikiDer > Высокая (вычислимость) - Википедия

High (computability) - Wikipedia

В теория вычислимости, а Степень Тьюринга [Икс] высока, если она вычислима в 0 ′, и Прыжок Тьюринга [Икс′] Равно 0 ′ ′, что является максимально возможной степенью с точки зрения Сводимость по Тьюрингу для скачка множества, которое вычислимо за 0 '(Soare 1987: 71).

Точно так же степень высокий n если его n-й прыжок является (n + 1) -м прыжком из 0. В более общем смысле, степень d является обобщенный высокий n если его n-й прыжок - это n-й прыжок соединения d с 0 ′.

Смотрите также

Низкая (вычислимость)

Рекомендации

Соаре, Р. Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag, Берлин, 1987. ISBN 3-540-15299-7