Степень Тьюринга
- Степень Тьюринга (или неразрешимость) измеряет уровень алгоритмической неразрешимости набора натуральных чисел.
- Понятие степени Тьюринга фундаментально в теории вычислимости.
- Степени Тьюринга частично упорядочены и соответствуют уровню алгоритмической неразрешимости множества.
- Степени Тьюринга введены Постом (1944) и исследованы Клини и Постом (1954).
- Структура степеней Тьюринга сложна и не является решеткой.
- Приоритетный метод является основным методом получения результатов о рекурсивно перечислимых множествах.
- Проблема построения промежуточной степени между 0 и 0′ (проблема Поста) была решена Фридбергом и Мучником в 1950-х годах.
Полный текст статьи: