🔢 mathematics

Finite Observations, Infinite Behaviour: bicategorical semantics for stateful monoidal processes

이 논문은 상태를 가진 모노이달 프로세스(stateful monoidal processes)에 대한 이범주적 의미론(bicategorical semantics)을 도입하여, 시스템을 내부 상태가 아닌 유한한 관찰 제약 조건에 기초하여 동일시하며, 피드백 범주(feedback categories)를 위한 함자적 프레임워크를 제공하고, 비결정론적 및 선형 시불변(linear time-invariant) 시스템을 포함한 다양한 프로세스 유형을 통합하는 범주화된 컴팩트성 정리(categorified compactness theorem)를 확립한다.

원저자: Cole Comfort, Giovanni de Felice

게시일 2026-07-07

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Cole Comfort, Giovanni de Felice

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 신비로운 기계를 이해하려고 노력하고 있다고 상상해 보십시오. 당신은 그 내부를 볼 수 없습니다. 기어, 메모리 칩, 혹은 내부 코드를 볼 수 없습니다. 당신이 할 수 있는 전부는 무엇이 들어가고 무엇이 나오는지 관찰하는 것뿐입니다.

이 논문은 서로 완전히 다르게 만들어졌음에도 불구하고, 두 신비로운 기계가 실제로 똑같은 일을 하고 있다고 언제 정의할 수 있는지에 관한 것입니다.

다음은 단순한 비유를 사용하여 그들의 아이디어를 정리한 내용입니다.

1. 문제: "블랙박스"의 미스터리

라디오, 주식 시장 알고리즘, 양자 컴퓨터와 같이 세상의 대부분 시스템은 **내부 상태(internal state)**를 가지고 있습니다. 이 상태는 숨겨진 일기장과 같습니다.

기존 방식: 두 기계가 같다고 말하기 위해, 수학자들은 보통 기계가 영원히 실행되는 것을 시뮬레이션하려고 했습니다. 그들은 "만약 기계 A와 기계 B가 가능한 모든 입력에 대해 정확히 동일한 무한한 출력 스트림을 생성한다면, 두 기계는 같다"라고 말하곤 했습니다.
문제점: 이 방식은 시스템이 복잡해질 때 무너집니다. 만약 기계가 **부분적(partial)**이거나(중간에 멈출 수 있음), **비결정론적(nondeterministic)**이거나(동전을 던져 결정을 내릴 수 있음), **확률적(probabilistic)**이거나(90%의 확률로 작동함), 혹은 **양자적(quantum)**이라면(여러 상태에 동시에 존재함), 당신은 항상 "무한한 미래"를 예측할 수는 없습니다. 시뮬레이션이 중간에 멈추거나 계산이 불가능해질 수 있기 때문입니다.

2. 해결책: "유한한 탐정" 접근법

저자들은 무한한 미래를 예측하는 대신, 새로운 규칙을 제안합니다: 우리는 실제로 관찰 가능한 유한한 시간 동안의 것에만 관심을 갖는다.

당신이 두 명의 용의자(기계)를 심문하는 탐정이라고 상상해 보십시오. 당신은 그들의 마음을 볼 수 없지만, 질문(입력)을 던지고 답변(출력)을 들을 수 있습니다.

규칙: 두 기계가 "같다"고 간주되는 기준은, 기계 A에 대해 실행할 수 있는 모든 유한한 테스트에 대해 기계 B도 (아마도 약간의 추가적인 맥락을 포함하여) 그 테스트를 통과할 수 있고, 그 반대도 마찬가지일 때입니다.
비유: 이것은 마치 두 사람이 동일 인물이라고 주장하는 것과 같습니다. 당신은 그들의 전체 인생사를 알 필요가 없습니다. 단지 사람 A에 대해 당신이 아는 모든 사실이 사람 B에게도 적용되는지 확인하면 됩니다. 만약 사람 A가 "나는 2020년에 파리에 있었다"라고 말했을 때, 사람 B 또한 파리에 있었다는 것을 확인할 수 있다면 이는 일치하는 것입니다. 만약 사람 A는 "나는 날 수 있다"라고 말하는데 사람 B는 그럴 수 없다면, 두 사람은 다른 사람입니다.

3. "버리기(Discard)" 개념: 잊는 것이 유용하다

이 논문은 **"Discard Bicategory"**라는 수학적 구조를 도입합니다.

은유: 어떤 대화에서 당신이 정보의 일부를 무시하기로 선택하는 상황을 상상해 보십시오. 만약 내가 긴 이야기를 하더라도 당신이 결말에만 관심이 있다면, 당신은 중간 내용을 "버리는(discard)" 것입니다.
중요한 이유: 현실 세계에서 우리는 종-종 시스템의 모든 세부 사항에 관심을 두지 않습니다. 우리는 컴퓨터의 내부 메모리보다는 오직 최종 결과에만 관심이 있을 수 있습니다. 이 수학은 저자들이 내부 상태를 순수하게 "버리고", 오직 입력과 출력 사이의 관계에만 집중할 수 있게 해줍니다.

4. "콤팩트성(Compactness)" 정리: 퍼즐 조각의 마법

이 논문의 가장 멋진 결과 중 하나는 "콤팩트성 정리"입니다.

비유: 거대한 무한 퍼즐을 가지고 있다고 상상해 보십시오. 당신은 한 번에 전체 그림을 볼 수 없습니다. 하지만 당신에게는 다음과 같은 규칙이 있습니다: 만약 어떤 유한한 퍼즐 조각들의 집합을 모았을 때 그것들이 서로 충돌하지 않고 잘 맞물린다면, 그렇다면 반드시 그 무한한 퍼즐 전체를 완벽하게 조립할 수 있는 방법이 존재한다.
결과: 저자들은 시스템에 대한 일관된 유한한 관측값(퍼즐 조각)이 있다면, 이를 수학적으로 결합하여 그 시스템의 행동에 대한 단일하고 완벽한 무한한 설명을 형성할 수 있음을 증명합니다. 이는 시스템이 "폐쇄 관계(closed relations, 예: 가능한 결과들의 집합)"처럼 작동할 때 특히 유효합니다.

5. 다루는 실제 사례들

저자들은 이 수학이 다양한 유형의 "기계"에 적용됨을 보여줍니다.

결정론적(Deterministic): 표준 컴퓨터 (예: 계산기).
비결정론적(Nondeterministic): 무작위 선택을 하는 기계 (예: 주사위를 굴리는 로봇).
확률적(Probabilistic): 확률을 다루는 기계 (예: 일기 예보 모델).
양자적(Quantum): 양자 물리학을 사용하는 기계 (예: 사물이 두 가지 상태에 동시에 존재할 수 있는 경우).

6. "시간"의 측면

이 논문은 시간 또한 아름답게 다룹니다.

은유: 영화 필름을 상상해 보십시오. 보통 우리는 처음부터 끝까지 영화를 봅니다. 하지만 이 수학을 사용하면 한 장면을 보고, 그다음 장면을 본 뒤, 그 사이의 "지연(delay)"이 이야기 자체를 바꾸지는 않는다는 것을 깨달을 수 있습니다.
결과: 저자들은 관측의 시간을 이동시키더라도(영화를 5분 늦게 보더라도), 기계의 근본적인 "행동"은 동일하게 유지된다는 것을 증명합니다. 이를 통해 그들은 영원히 실행되는 시스템(예: 신호 흐름 그래프)을 하나의 통합된 객체로 다룰 수 있습니다.

요약

요컨대, 이 논문은 복잡하고 상태를 가진 기계를 설명하기 위한 새로운 수학적 언어를 제공합니다. 기계의 무한한 내부 삶을 시뮬레이션하려고 애쓰며 매몰되는 대신, 이 논문은 이렇게 말합니다: "두 기계가 동일한 유한한 테스트를 통과한다면, 그들은 같다."

이 접근 방식은 무작위적이거나 양자적인 시스템까지도 처리할 수 있을 만큼 견고하며, 충분히 일관된 국소적 관측값이 있다면 시스템의 전체 무한한 행동을 재구성할 수 있음을 증명합니다. 이는 우리가 볼 수 없는 것이 아니라, 실제로 볼 수 있는 것에 기반하여 기계의 "정체성"을 정의하는 방법입니다.

기술 요약: 유한한 관측, 무한한 행동

문제 정의

신호 흐름 그래프(signal flow graphs), 확률 과정(stochastic processes), 메모리를 가진 양자 채널(quantum channels with memory)과 같은 시간 의존적 시스템은 종종 내부 메모리를 유지하는 상태 기반 프로세스(예: Mealy machine)로 모델링됩니다. 그러나 결정론적 시스템의 행동은 공공층적 고정점(coinductive fixed points)을 통해 잘 이해되는 반면, 이러한 특성은 프로세스가 부분적이거나, 비결정론적이거나, 확률적이거나, 양자적인 경우 무너집니다. 이러한 설정에서는 공공층적 고정점이 존재하지 않을 수 있으며, 표준적인 행동적 동치(behavioral equivalence)의 정의가 실패합니다.

이 연구를 이끄는 핵심 질문은 다음과 같습니다: 두 상태 기반 프로세스가 언제 동일한 무한 행동을 생성하는가? 저자들은 사전적인 전역 제약 조건에 의존하기보다, 오직 유한하고 국소적인 관측에만 의존하는 데노테이셔널(denotational) 답변을 찾고자 합니다. 과제는 두 프로세스가 (내부 상태와 독립적으로) 유한한 관측에 의해 결정된 입력 및 출력에 대해 동일한 제약을 가할 때 두 프로세스가 동등하다고 정의되는 의미론적 구조를 만드는 것입니다.

방법론

1. 구조적 기초: 디스카드 비카테고리 (Discard Bicategories)

저자들은 **디스카드 비카테고리(discard bicategory)**라고 불리는 구조적 프레임워크를 도입합니다. 이는 정보를 무시하는 능력(discard morphism, $\top_X: X \to I$ )을 갖춘, 프리오더 인리치드 대칭 단사 카테고리(preorder-enriched symmetric monoidal category)입니다.

프리오더 인리치먼트 (Preorder Enrichment): 호름 셋(Hom-sets)은 프로세스의 정보성(근사치)을 비교할 수 있게 해주는 프리오더( $\subseteq$ )를 갖습니다.
디스카드의 락스 자연성 (Lax Naturality of Discard): 디스카드 연산은 근사( $\top_Y \circ f \subseteq \top_X$ )와 호환됩니다. 즉, 프로세스를 실행한 후 버리는 것은 입력을 직접 버리는 것보다 정보성이 낮습니다.
범위: 이 구조는 부분 함수(제한 순서), 관계(부분 집합 포함), 확률 커널(조건부 순서), 양자 채널(순수화 순서)을 포함한 다양한 프로세스 이론을 통합합니다.

2. 의미론적 구성: 행동의 카테고리

핵심 기여는 행동의 디스카드 비카테고리, $\text{Obs}_{I,J}(\mathcal{C})$ 를 구축하는 것입니다.

컨텍스트 (Contexts): 이 구성은 인덱스 집합 $I$ (시간 또는 공간을 나타냄)와 $I$ 의 유한 부분 집합들의 모임 $J$ (컨텍스트)에 의해 매개변수화됩니다.
단조 가족 (Monotone Families): 행동은 관측의 "단조 가족"으로 정의됩니다. 이는 각 $f_j$ 가 유한한 컨텍스트 $j$ 에 제한된 프로세스를 설명하는 모피즘의 가족 $\{f_j\}_{j \in J}$ 입니다.
일관성 조건 (Consistency Condition): 가족은 일관되어야 합니다. 즉, 더 큰 컨텍스트 $j'$ 에서의 관측은 더 작은 컨텍스트 $j$ 에서의 관측을 정교화해야 합니다 (형식적으로, $(1 \otimes \top) \circ f_{j'} \subseteq f_j \otimes \top$ ).
관측적 동치 (Observational Equivalence): 두 프로세스는 모든 관측이 다른 하나의 관측에 의해 (아마도 더 큰 컨텍스트 내에서) 검증될 수 있을 때 관측적으로 동등하다고 식별됩니다. 이는 상호 근사( $f \subseteq g$ 및 $g \subseteq f$ )로 공식화됩니다.
quotienting (몫): 행동의 카테고리는 단조 넷(monotone nets)을 이 관측적 동치 관계로 몫을 취하여 얻어집니다.

3. 상태 기반 프로세스와의 통합

저자들은 이 구성이 상태 기반 프로세스를 위한 함수적 의미론을 제공함을 보여줍니다.

상태 재매개변수화 (State Reparametrization): 이 구성은 내부 상태의 디나투럴(dinatural) 재매개변수화에 의해서만 달라지는 상태 기반 프로세스들을 식별합니다.
시간 지연 (Time Delay): 시간 지연 연산은 자연 변환임이 입증되었습니다. 컴팩트-클로즈드(compact-closed) 설정에서 이는 자연 동형이 되며, Katis, Sabadini, Walters의 피드백 카테고리를 형성할 수 있게 합니다.
불일치 전파 (Inconsistency Propagation): 기존의 스트림 의미론(예: 코알제브라적 스트림, 외연적 스트림)과 달리, 이 구성은 불일치를 전역적으로 전파합니다. 만약 프로세스가 단 하나의 유한한 컨텍스트에서라도 불일치한다면, 그 전체 행동은 제로 모피즘(zero morphism)이 됩니다.

주요 결과

1. 균일성 및 함수성

이 구성은 부분적, 비결정론적, 확률적, 양자 프로세스에 균일하게 적용됩니다. 이는 베이스 체인지(base change)에 대해 함수적이며, 이는 기초 프로세스 이론 사이의 모피즘이 각각의 행동 카테го리에 대한 모피즘을 유도함을 의미합니다.

2. 범주화된 컴팩트성 정리 (The Categorified Compactness Theorem)

비결정론적 설정(관계)에 집중하여, 저자들은 범주화된 컴팩트성 정리(정리 5.5)를 증명합니다.

진술: 컴팩트 하우스도르프 공간 사이의 닫힌 관계(closed relations)에 대한 카테고리에서, 모든 호환 가능한 유한 관측의 가족(단조 넷)은 단일한 무한 닫힌 관계로 유일하고 함수적으로 확장됩니다.
의의: 이는 특정 설정에서 국소적 일관성이 전역적 존재성과 유일성을 보장함을 확립하며, 효과적으로 유한한 관측들을 하나의 전역적 행동으로 "풀칠(gluing)"합니다.

3. Willems의 행동 복구

아핀 관계(affine relations)를 가진 유한 체(finite fields) 위로 제한될 때, 이 컴팩트성 정리는 Willems의 행동 개념을 회복합니다.

저자들은 초기화되지 않은 LTI 시스템에 대한 자신들의 시간 영역 의미론이, 상수 계수 차분 방정식 시스템의 커널로서 정의된 Willems의 행동을 정확히 포착함을 보여줍니다.
이는 신호 흐름 그래프에 대한 합성 가능한 시간 영역 의미론을 제공하며, 이는 주로 주파수 영역(z-도메인) 해석에 의존했던 기존의 범주적 처리를 넘어선 것입니다.

4. 기존 의미론과의 비교

본 논문은 기존의 접근 방식들(상태 기반 모피즘 시퀀스, 코알제브라적 스트림, 인과적 시퀀스)이 모든 바람직한 속성을 동시에 만족시키지 못한다고 주장합니다:

상태 기반 모피즘 시퀀스는 순수하게 국소적이며 불일치를 무한히 전파하지 못합니다.
코알제브라적 스트림은 부분성이나 제로 모피즘이 존재하는 경우 붕괴합니다(무정형이 됨).
인과적/단조 시퀀스는 디나투럴리 동등한 스트림들을 식별하지 못합니다.
제안된 구성은 유한한 관측의 일관성을 우선시함으로써 이러한 문제들을 해결합니다.

의의 및 주장

이 논문은 공공층적 고정점이 존재하지 않을 수 있는 상황에서도, 상태 기반 시스템의 무한 행동을 정의하기 위한 프로세스 이론적 해결책을 제공한다고 주장합니다. 내부 상태에서 유한한 제약으로 초점을 전환함으로써, 저자들은 다음을 수행하는 견고한 의미론적 프레임워크를 제시합니다:

다양한 프로세스 이론(결정론적, 부분적, 확률적, 양자적)에 걸쳐 행동적 동치를 일반화합니다.
로컬 관측과 글로벌 행동 사이의 관계를 통합하며, 특정 위상적 조건(컴팩트 하우스도르프 공간) 하에서 국소적 관측이 전역적 행동을 유일하게 결정함을 증명합니다.
범주적 의미론을 고전적 시스템 이론과 화해시켜, 유한 체 위에서의 LTI 시스템에 대한 Willems의 행동적 접근법을 합성 가능한 시간 영역 프레임워크 내에서 정확히 회복합니다.

저자들은 이 연구를 기초적인 단계로 위치시키며, 행동의 존재와 그 속성을 확립했지만, 이 행동들을 위한 그래픽 언어(공리계)의 완전성은 향후 연구 과제로 남아 있다고 언급합니다. 또한, 컴팩트성 정리를 확률적 및 양자적 설정으로 일반화하는 것이 자연스러운 다음 단계임을 시사합니다.