Арифметическая иерархия

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

Definition

Арифметическая иерархия стратифицирует множества, определимые в арифметике первого порядка, путем подсчета чередований неограниченных кванторов перед вычислимой матрицей, при этом сигма-n множества определяются блоком, начинающимся с квантора существования, а пи-n множества — блоком, начинающимся с квантора всеобщности.

Scope

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

Core questions

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

Key theories

Классификация по кванторам

Множество является сигма-n, если оно определимо n чередующимися блоками кванторов, начинающимися с квантора существования над вычислимым отношением, и пи-n, если оно начинается с квантора всеобщности; вычислимо перечислимые множества — это в точности сигма-один множества.

Теорема Поста

Множество является сигма-(n+1) тогда и только тогда, когда оно вычислимо перечислимо относительно n-го скачка Тьюринга, что связывает уровни иерархии с итерированными релятивизованными проблемами остановки.

Строгость иерархии

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

Clinical relevance

Арифметическая иерархия является стандартным мерилом сложности определимых проблем в логике и информатике: она локализует такие проблемы, как тотальность, конечность и соконечность вычислимых множеств на точных уровнях, и очерчивает границу между тем, что является вычислимо перечислимым, и тем, что требует более сильных невычислимых ресурсов.

History

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

Key figures

• Stephen Cole Kleene
• Andrzej Mostowski
• Emil Post

Seminal works

• rogers1987
• soare1987
• cutland1980

Frequently asked questions

Что означает более высокий уровень в иерархии?

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

Где находятся вычислимо перечислимые множества?

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