기술 요약: 관찰자, 대칭성, 그리고 언어 클래스의 계층 구조

문제 정의

고전적 계산 복잡도 및 형식 언어 이론은 전통적으로 계산 기계의 계산 능력(예: 유한 오토마타, 푸시다운 오토마타, 튜링 기계)에 기반하여 문제를 분류하며, 입력이 완전히 접근 가능한 정렬된 기호 시퀀스라고 가정한다. 본 논문은 이러한 관점을 뒤집어, 계산 시스템의 한계가 기계의 처리 능력에서 오는 것이 아니라 관찰자의 구조로부터 발생할 수 있다고 상정한다.

본 논문이 다루는 핵심 문제는 다음과 같다: 계산 시스템이 전체 입력 문자열을 직접 사용하는 대신, 특정 투영(projection) 또는 변환된 형태만을 접하게 될 때, 해당 시스템이 인식할 수 있는 언어는 무엇인가? 본 논문은 관찰자 함수 $O: \Sigma^* \to S$(입력 문자열을 관찰 공간 $S$로 매핑하는 함수)의 "맹목성(blindness)" 또는 "구조적 제한"이 기계의 계산 모델과 무관하게 인식 가능한 언어의 클래스를 어떻게 결정하는지를 조사한다.

방법론

본 논문은 관찰자(observer) 개념을 중심으로 하는 공식 프레임워크를 도입한다:

1. 관찰자 정의: 관찰자는 입력 문자열 $x$를 관찰값 $O(x)$로 변환하는 함수이다. 계산 시스템 $(M, O)$는 $x$ 대신 $O(x)$를 입력으로 받는다.
2. O-포화(O-Saturation): 언어 $L$이 O-포화되어 있다는 것은 $L$의 멤버십이 오직 관찰 $O(x)$에만 의존함을 의미한다. 형식적으로, $x \sim_O y \implies (x \in L \iff y \in L)$이다. 만약 어떤 언어가 O-포화되어 있지 않다면, 관찰자 $O$를 갖춘 기계는 기계의 계산 능력과 관계없이 해당 언어를 결정할 수 없다.
3. 관찰적 순서(Observational Order): 관찰자들 사이의 전순서(preorder) $\preceq$를 정의한다. 여기서 $O_1 \preceq O_2$는 $O_1$이 $O_2$로부터 유도될 수 있음($O_1 = f \circ O_2$)을 의미한다. 이는 언어 클래스의 계층 $\mathcal{L}(O)$를 유도하며, $O_1 \preceq O_2 \implies \mathcal{L}(O_1) \subseteq \mathcal{L}(O_2)$를 만족한다.
4. 표준 관찰자(Canonical Observers): 계층 구조를 구축하기 위해 다음과 같은 특정 관찰자들을 정의한다:
   • $O_\perp$: 자명한 관찰자 (모든 문자열을 상수로 매핑).
   • $O_{len}$: 길이 관찰자 (길이 $|x|$로 매핑).
   • $O_{par}$: 패리티 관찰자 (2에 대한 나머지 값으로 매핑).
   • $O_{prof}$: 프로필 관찰자 (순서를 무시한 기호 출현 횟수의 벡터로 매핑).
   • $O_k$: 부분 수열 관찰자 (길이가 $k$ 이하인 부분 수열의 집합으로 매핑).
   • $O_\top$: 완전한 관찰자 (항등 함수, $O(x) = x$).

주요 기여 및 결과

1. 순서-맹목 오토마타와 순열-폐쇄 언어

본 논문은 순서(sequence)가 아닌 문자열의 프로필(기호 횟수의 멀티셋)을 처리하는 **순서-맹목 오토마타(order-blind automaton)**를 규명한다.

• 정리 2.5: 어떤 언어가 순서-맹목 오토마타에 의해 인식 가능할 필요충분조건은 그 언어가 순열-폐쇄(permutation-closed)(기호 재배열에 대해 불변)인 것이다.
• 이 결과는 상태의 유한성이 주요 제약이 아니라, 관찰자가 클래스를 결정한다는 점을 보여준다. 자명한 관찰자를 가진 튜링 기계조차 $\emptyset$와 $\Sigma^*$만을 인식할 수 있다.

2. 관찰적 계층 구조

본 논문은 표준 관찰자의 관찰 능력을 바탕으로 언어 클래스의 부분 순서(partial order)를 구축한다. 계층 구조는 다음과 같은 특성을 보인다:

• 다이아몬드 형태의 프로필 부격자(Sub-lattice):
  • $O_\perp \prec O_{len} \prec O_{prof} \prec O_\top$ (길이 분기)
  • $O_\perp \prec O_{par} \prec O_{prof} \prec O_\top$ (패리티 분기)
  • $O_{len}$과 $O_{par}$는 비교 불가능하다.
• 무한 부분 수열 분기:
  • $O_\perp \prec O_1 \prec O_2 \prec \dots \prec O_\top$.
  • 이 분기는 Simon의 piecewise testable 언어 계층과 일치한다.
• 직교성(Orthogonality): 프로필 부격자(계수 정보)와 부분 수열 분기(부분 순서 정보)는 서로 **직교(비교 불가능)**한다. 즉, $O_{prof}$는 임의의 $O_k$와 비교 불가능하다.

3. Chomsky 계층과의 직교성

본 논문은 관찰적 계층이 Chomsky 계층(정규, 문맥 자유 등)과 엄격히 **직교(incomparable)**함을 증명한다.

• 정규 언어이지만 O-포화되지 않은 언어가 존재한다 (예: $0^*1^*$는 $O_{prof}$-포화가 아니다).
• O-포화되어 있지만 정규 언어가 아닌 언어가 존재한다 (예: $\{x \mid |x|_0 = |x|_1\}$는 $O_{prof}$-포화이지만 정규 언어가 아니다).
• 이는 "구조적 맹목성"과 "계산 복잡도"가 독립적인 분류 축임을 입증한다.

4. Simon의 계층과의 연결

본 논문은 piecewise testable 언어에 관한 Simon의 정리를 재구성한다.

• 관찰자 가족 $\{O_k\}$는 Simon의 계층에 나타나는 동치 관계와 정확히 일치한다.
• 정규 언어가 piecewise testable할 필요충분조건은 어떤 $O_k$에 의해 결정 가능하다는 것이다.
• 프로필 클래스 $\mathcal{L}(O_{prof})$와 piecewise testable 언어들의 합집합 $\bigcup_k \mathcal{L}(O_k)$는 서로 비교 불가능하다.

5. 관찰자 매개 복잡도 클래스 (PO 및 NPO)

이 프레임워크는 복잡도를 입력 크기 $|x|$가 아닌 관찰의 크기 $|enc(O(x))|$에 대해 측정하는 복잡도 이론으로 확장된다.

• 구조적 붕괴(Structural Collapse): 본 논문은 $PO_{prof} = NPO_{prof}$임을 증명한다.
  • 의미: 이것은 $P$ 대 $NP$문제의 해결이 아니다. 대신, 관찰자$O_{prof}$가 모든 조합적 구조(순서)를 제거하기 때문에 발생하는 구조적 붕골이다. 순서가 사라지면 비결정론은 결정론에 비해 어떠한 이점도 제공하지 못한다.
  • 엄격한 포함 관계: $PO_{prof} \subsetneq P$이다. $PO_{prof}$는 프로필 크기에 대해 다항 시간 내에 계산 가능한 $O_{prof}$-포화 언어만을 포함한다. $0^*1^*$는 $P$에 속하지만 $O_{prof}$-포화가 아니므로, 이 포함 관계는 엄격하다.
• 난해함과 맹목성의 독립성: 본 논문은 계산적 난해함과 관찰적 결정 가능성이 독립적임을 보여준다. $P$에 속하지만 $O_{prof}$-포화가 아닌 언어가 존재하며, $O_{prof}$-포화이지만 RE(재귀적 열거) 클래스 밖에 있는 언어도 존재한다 (예: 기호 횟수에 대한 정지 문제로 정의된 언어).

의의 및 주장

본 논문은 형식 언어와 계산 문제를 분류하기 위한 새로운 독립적 축을 도입한다고 주장한다. 주요 의의는 다음과 같다:

1. 기계의 능력과 관찰자 구조의 분리: 관찰자의 "약함"이 튜링 기계조차 문제를 풀 수 없게 만들 수 있는 반면, 더 약한 기계(예: DFA)가 더 강한 관찰자를 통해 문제를 해결할 수 있음을 확립한다.
2. 난해함(Hardness)과 맹목성(Blindness)의 구분: 알고리즘 복잡도로 인한 계산적 난해함과 정보 손실로 인한 구조적 맹목성을 명확히 구분한다. $PO_{prof} = NPO_{prof}$라는 붕괴는, 이 붕괴가 비결정론이 본질적으로 약해서가 아니라 관찰자가 문제를 어렵게 만드는 바로 그 구조를 제거했기 때문에 발생한다는 점을 통해 두 현상이 별개임을 보여준다.
3. 물리적 해석: 본 프레임워크는 거시적 관찰자(온도나 밀도 같은 총량만을 보는 관찰자)가 서로 순열 관계에 있는 미시적 이력들을 구분할 수 없다는 통계 역학의 개념에 대한 수학적 유사성을 제공한다. 이는 "열역학적 비가역성"을 관찰적 속성으로서의 개념으로 다루는 수학적 기초를 제공한다.

결론적으로, 본 논문은 관찰적 계층이 정보가 본질적으로 제한되거나 집계되는 시스템을 분석하기 위한 엄격한 프레임워크를 제공하며, 향후 연구가 확률적 관찰자, 관찰자의 범주적 합성, 그리고 관찰적 복잡도와 정보 보존 사이의 정량적 관계를 탐구해야 함을 시사한다.