Вычислимо перечислимые множества и степени Тьюринга

Вычислимо перечислимые множества — это те, члены которых могут быть эффективно перечислены, а степени Тьюринга ранжируют все множества по относительной вычислимости, организуя ландшафт неразрешимых проблем.

Definition

Множество является вычислимо перечислимым, если некоторый алгоритм перечисляет точно его члены; множество сводимо по Тьюрингу к другому, если оно может быть вычислено с использованием другого в качестве оракула, а классы эквивалентности при взаимной сводимости являются степенями Тьюринга, частично упорядоченными по относительной вычислимости.

Scope

Эта тема охватывает вычислимо перечислимые множества и их основные свойства, сводимость по Тьюрингу и частичный порядок степеней, множество останова как полное перечислимое множество, проблему Поста и ее разрешение методом приоритетов, а также структурную теорию вычислимо перечислимых степеней.

Core questions

• В чем разница между вычислимым и просто вычислимо перечислимым множеством?
• Как сводимость по Тьюрингу сравнивает сложность двух множеств?
• Существуют ли вычислимо перечислимые степени строго между вычислимыми множествами и проблемой останова?
• Какова глобальная структура степеней неразрешимости?

Key theories

Дополнение и множество останова

Множество вычислимо тогда и только тогда, когда оно само и его дополнение являются вычислимо перечислимыми, а множество останова является вычислимо перечислимым, но не вычислимым, каноническим полным перечислимым множеством.

Проблема Поста и метод приоритетов

Пост задался вопросом, существуют ли вычислимо перечислимые степени строго между вычислимыми множествами и проблемой останова; Фридберг и Мучник ответили утвердительно, изобретя метод приоритетов с конечным ущербом.

Структура степеней

Степени Тьюринга и вычислимо перечислимые степени образуют богатые, плотно упорядоченные структуры, изучаемые с помощью продвинутых приоритетных конструкций, раскрывающих сложные свойства определимости и вложения.

Clinical relevance

Теория степеней обеспечивает тонкую классификацию неразрешимых проблем, показывая, что неразрешимость имеет бесконечно много строго возрастающих уровней, а метод приоритетов, разработанный для их изучения, является центральным методом доказательства, который повлиял на обратную математику и анализ алгоритмической случайности.

History

Пост ввел вычислимо перечислимые множества и поставил свою проблему в 1944 году, задавшись вопросом, существуют ли неполные невычислимые перечислимые степени. Фридберг и Мучник независимо решили ее около 1956 года с помощью метода приоритетов, который стал основным инструментом для глубокого структурного изучения степеней, проводимого Саксом, Соаром и многими другими.

Key figures

• Emil Post
• Richard Friedberg
• Albert Muchnik
• Robert Soare

Seminal works

• soare1987
• post1944
• rogers1987

Frequently asked questions

Что такое оракул в теории вычислимости?

Оракул — это внешний источник, который мгновенно отвечает на вопросы о принадлежности к фиксированному множеству. Машина с оракулом может использовать эти ответы во время своих вычислений, а сводимость по Тьюрингу спрашивает, может ли одно множество быть вычислено машиной, оснащенной другим множеством в качестве оракула.

Почему проблема Поста была значимой?

Она задавалась вопросом, имеет ли неразрешимость промежуточные уровни среди вычислимо перечислимых множеств, между разрешимыми и проблемой останова. Положительный ответ выявил тонкую структуру степеней и потребовал метода приоритетов, мощной новой техники, которая сформировала всю предметную область.