산술적 위계

산술적 위계는 자연수 집합을 정의하는 데 필요한 교대 한정자(alternating quantifiers)의 수에 따라 분류하며, 논리적 복잡성과 계산 불가능성(uncomputability)의 정도를 연결합니다.

Definition

산술적 위계는 계산 가능한 행렬(computable matrix) 앞에 오는 무한 한정자(unbounded quantifiers)의 교대 횟수를 세어 1차 산술(first-order arithmetic)에서 정의 가능한 집합들을 계층화합니다. 시그마-n 집합은 존재 한정자(existential quantifier)로 시작하는 블록으로 정의되고, 파이-n 집합은 전체 한정자(universal quantifier)로 시작하는 블록으로 정의됩니다.

Scope

이 주제는 계산 가능한 관계(computable relations)에 대한 한정자 교대(quantifier alternation)를 통해 정의 가능한 집합을 시그마(sigma), 파이(pi), 델타(delta) 수준으로 분류하는 것, 포스트 정리(Post's theorem)가 위계를 반복된 정지 문제(iterated halting problem) 및 튜링 점프(Turing jumps)와 연결하는 것, 위계의 엄격성(strictness), 그리고 해석적 위계(analytical hierarchy)로의 확장을 다룹니다.

Core questions

• 한정자 교대는 집합의 복잡성을 어떻게 측정하는가?
• 각 수준의 시그마, 파이, 델타 클래스는 서로 어떻게 관련되는가?
• 이 위계는 정지 문제의 반복과 어떻게 상응하는가?
• 이 위계는 왜 엄격하며, 각 수준이 이전 수준보다 왜 더 큰가?

Key theories

한정자 분류

집합이 계산 가능한 관계에 대해 존재적으로 시작하는 n개의 교대 한정자 블록으로 정의 가능하면 시그마-n이고, 전체적으로 시작하면 파이-n입니다. 계산 가능하게 열거 가능한 집합은 정확히 시그마-1 집합입니다.

포스트 정리

집합이 n번째 튜링 점프에 대해 계산 가능하게 열거 가능할 때 정확히 시그마-(n+1)이며, 이는 위계의 수준을 반복된 상대화된 정지 문제(relativized halting problems)와 연결합니다.

위계의 엄격성

각 튜링 점프는 이전 점프보다 엄격하게 더 복잡하므로, 산술적 위계의 모든 수준은 그 아래 수준들을 적절히 포함하며 위계는 붕괴되지 않습니다.

Clinical relevance

산술적 위계는 논리학 및 컴퓨터 과학에서 정의 가능한 문제의 복잡성을 측정하는 표준 척도입니다. 이는 계산 가능한 집합의 전체성(totality), 유한성(finiteness), 여유한성(cofiniteness)과 같은 문제들을 정확한 수준에 위치시키고, 계산 가능하게 열거 가능한 것과 더 강력한 비계산적 자원(noncomputable resources)을 요구하는 것 사이의 경계를 설정합니다.

History

클레이니(Kleene)와 모스토프스키(Mostowski)는 1943년경 독립적으로 산술적 위계를 도입하여, 계산 가능한 술어(computable predicates)에 대한 한정자 복잡성(quantifier complexity)에 따라 집합을 분류했습니다. 포스트 정리는 이 위계를 튜링 점프와 연결하여 정의 가능성 기반 관점과 계산 가능성 기반 관점을 통합했으며, 이 프레임워크는 나중에 해석적 위계로 확장되었습니다.

Key figures

• Stephen Cole Kleene
• Andrzej Mostowski
• Emil Post

Seminal works

• rogers1987
• soare1987
• cutland1980

Frequently asked questions

위계에서 더 높은 수준은 무엇을 의미합니까?

더 많은 교대 한정자는 더 복잡한 정의를 의미하며, 포스트 정리에 따르면, 결정하기 위해 정지 문제의 더 많은 반복을 요구하는 문제입니다. 위계에서 더 높은 집합은 그 아래 집합들보다 계산에 대한 접근성이 엄격하게 낮습니다.

계산 가능하게 열거 가능한 집합은 어디에 위치합니까?

이들은 시그마-1 수준에 위치하며, 계산 가능한 관계에 대한 단일 존재 한정자로 정의될 수 있습니다. 이들의 여집합은 파이-1 수준에 위치하며, 둘 다인 델타-1 집합은 정확히 계산 가능한 집합입니다.