💻 computer science

When Equality Fails as a Rewrite Principle: Provenance and Definedness for Measurement-Bearing Expressions

이 논문은 측정값을 포함하는 표현식에서 대수적 등식이 재작성 원리로 작동하지 않는 문제를 해결하기 위해, 관측의 재사용과 정의역을 추적하는 통합된 의미론을 제안하고 이를 Lean 4 로 완전히 형식화했습니다.

원저자: David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz

게시일 2026-04-10

📖 4 분 읽기☕ 가벼운 읽기

원저자: David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz

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

이 논문은 **"수학적으로 똑같아 보이는 식도, 실제로는 완전히 다를 수 있다"**는 놀라운 사실을 측정 (Measurement) 이 포함된 상황에서 설명합니다.

일반적인 학교 수학에서는 $x - x = 0$ 이고, $x / x = 1$ 이라고 배웁니다. 하지만 이 논문은 **"실제 실험 데이터를 다룰 때는 이 공식이 항상 맞지 않다"**고 경고하며, 왜 그런지 그 이유를 아주 정교하게 설명합니다.

이 복잡한 논리를 일상적인 비유로 쉽게 풀어보겠습니다.

🍎 핵심 비유: "동일한 사과" vs "다른 사과"

이 논문의 핵심은 **'어디서 온 데이터인가 (Provenance)'**와 '언제까지 쓸 수 있는가 (Definedness)' 두 가지 문제입니다.

1. 문제 상황: "사과 두 개를 빼면?"

상상해 보세요. 여러분은 사과 무게를 재는 실험을 하고 있습니다.

상황 A (한 개의 사과): 여러분이 하나의 사과를 저울에 올렸다가, 그 값을 기록하고 다시 그 같은 사과를 빼는 시뮬레이션을 합니다.
- 수학식: $x - x$
- 결과: 당연히 0이 됩니다. (같은 물체니까)
상황 B (두 개의 사과): 여러분이 서로 다른 두 개의 사과를 각각 저울에 올렸습니다. 두 사과 모두 "무게가 100g~110g 사이"라고 측정되었습니다.
- 수학식: $x_1 - x_2$
- 결과: 0 이 아닐 수도 있습니다! 첫 번째 사과는 100g, 두 번째는 110g일 수 있으니까요.

💡 교훈: 수학 기호 ( $x$ ) 가 같아도, 그 뒤에 숨겨진 **'실제 사본 (데이터의 출처)'**이 하나인지 두 개인지에 따라 결과가 달라집니다. 기존 수학은 이 차이를 무시하고 무작정 $x-x=0$ 이라고 단순화해 버리지만, 과학적 데이터에서는 이는 치명적인 오류가 될 수 있습니다.

2. 두 번째 문제: "0 으로 나누는 함정"

다음은 나눗셈의 문제입니다.

상황: $x / x$ 라는 식이 있습니다. $x$ 가 0 이 아니면 항상 1 입니다.
문제: 하지만 만약 $x$ $x$ 가 0 일 수도 있는 데이터라면?
- $x / x$ 는 $x=0$ 일 때 **계산이 불가능 (에러)**해집니다.
- 반면, 그냥 숫자 1은 어디든 쓸 수 있습니다.
비유:
- 1은 "어디서나 먹을 수 있는 빵"입니다.
- $x/x$ 는 "빵이지만, $x$ 라는 재료가 0 이면 빵이 만들어지지 않는" 특수한 빵입니다.
- 만약 여러분이 "빵 ( $x/x$ )"을 "일반 빵 (1)"으로 바꾸는 건 안전합니다 (불가능한 상황을 피하니까).
- 하지만 "일반 빵 (1)"을 "특수 빵 ( $x/x$ )"으로 바꾸는 건 위험합니다. 갑자기 빵을 만들 수 없는 상황이 생길 수 있으니까요.

💡 교훈: "값이 같을 때"와 "언제나 쓸 수 있을 때"는 다릅니다. 수학적 등식은 '값'만 보지만, 과학적 계산은 '쓰일 수 있는 범위 (정의역)'도 봐야 합니다.

🛠️ 이 논문이 제안한 해결책: "데이터의 여권과 안전 수칙"

저자들은 이 두 가지 문제를 해결하기 위해 새로운 **'언어 (세마틱)'**를 만들었습니다.

데이터의 여권 (Token Provenance):
- 각 측정값에 고유한 **ID (여권)**를 붙입니다.
- $x - x$ 를 계산할 때, 두 $x$ 가 같은 여권을 가지고 있는지 확인합니다.
- 여권이 같으면 $0$으로 처리하고, 여권이 다르면 "아직 0 이라고 단정할 수 없다"고 경고합니다.
안전 수칙 (Admissible Domain):
- 계산식이 언제까지 안전하게 작동하는지 확인합니다.
- $x/x$ 를 $1 $로 바꿀 때,$ x$가 0 이 될 위험이 있는지 확인합니다.
- 위험이 있으면 "아직 바꾸면 안 돼"라고 막습니다.

🎭 이 논문이 발견한 놀라운 사실들

이 논문을 통해 저자들은 다음과 같은 중요한 결론을 내렸습니다.

단순한 등식은 위험하다: "값이 같으니 바꿔도 돼"라는 생각은 측정 데이터에서는 통하지 않습니다.
한쪽 방향만 안전하다: 복잡한 식을 간단한 식으로 바꾸는 것 (단순화) 은 안전할 수 있지만, 그 반대로 바꾸는 것은 위험할 수 있습니다. (예: $x/x$ 를 $1$로 바꾸는 건 OK, $1 $을$ x/x$로 바꾸는 건 NO)
서로 다른 두 가지가 모두 필요하다:
- 데이터의 출처 (여권) 만 알면 안 됩니다.
- 계산의 안전 범위 (안전 수칙) 만 알면 안 됩니다.
- 둘을 모두 고려해야만 안전한 계산이 가능합니다.

🏁 결론: 왜 이 논문이 중요한가?

이 논문은 **"컴퓨터가 과학 실험 데이터를 다룰 때, 단순히 수학적 공식만 믿고 계산을 해서는 안 된다"**는 것을 증명합니다.

마치 비행기 조종사가 "이 비행기는 수학적으로 날아갈 수 있다"고만 믿지 않고, "날씨가 나쁘면 날 수 없다 (안전 수칙)"와 "이 비행기는 이 엔진을 썼다 (데이터 출처)"를 모두 확인해야 안전한 비행을 할 수 있는 것과 같습니다.

저자들은 이 복잡한 규칙들을 Lean 4라는 컴퓨터 프로그램 언어로 완벽하게 증명했습니다. 즉, "우리가 만든 이 새로운 계산 규칙은 수학적으로 100% 확실하다"라고 컴퓨터가 검증해 준 것입니다.

한 줄 요약:

"데이터의 출처 (누구의 것?) 와 계산의 안전성 (언제까지 쓸 수 있는가?) 을 함께 확인하지 않으면, 과학적 계산은 엉뚱한 결과를 낼 수 있다."

1. 문제 제기 (Problem)

과학적 계산 및 측정 데이터 처리에서 수학적 등식 (Algebraic Equality) 을 기반으로 한 식의 단순화 (Rewrite/Simplification) 는 종종 안전하지 않습니다. 논문은 측정값을 포함하는 표현식을 다룰 때 등식이 재작성 원리로 작동하지 않는 두 가지 주요 실패 모드를 지적합니다.

기원 (Provenance) 의 부재:
- 동일한 관측치 (measurement) 가 식 내에서 두 번 사용될 때와, 서로 다른 두 관측치가 동일한 값을 가질 때를 구분하지 못합니다.
- 예: $x - x = 0$ 은 $x$ 가 하나의 측정 토큰 (동일한 관측치) 을 의미할 때만 유효합니다. 반면, $x_1 - x_2$ (서로 다른 관측치) 를 0 으로 치환하는 것은 일반적으로 타당하지 않습니다. 기존의 구간 산술 (Interval Arithmetic) 등은 이러한 '토큰의 재사용'과 '유사한 측정값의 사용'을 구분할 수 없습니다.
정의역 (Definedness) 의 문제:
- 나눗셈 연산은 특이점 (Singularity, 분모가 0 인 경우) 을 도입합니다.
- 예: $x/x$ 는 $x \neq 0$ 일 때 1 이지만, $x=0$ 에서는 정의되지 않습니다. 반면 상수 1 은 모든 곳에서 정의됩니다.
- 대수적으로 동일한 함수처럼 보이는 두 식 ( $x/x$ 와 $1$) 이 정의역에서 다를 수 있으며, 특이점을 제거하는 방향의 단순화는 안전하지만, 특이점을 도입하는 방향은 안전하지 않습니다.

이러한 문제들로 인해 기존의 대수적 등식 기반 단순화 기법은 과학적 측정 데이터에 적용 시 오류를 발생시키거나, 한 방향으로만 적용 가능한 (일방향) 제한을 갖게 됩니다.

2. 방법론 (Methodology)

저자들은 측정 표현식의 안전한 재작성을 위해 통일된 의미론 (Unified Semantics) 프레임워크를 제안합니다. 이 프레임워크는 두 가지 핵심 축을 동시에 추적합니다.

토큰 민감도 (Token Sensitivity): 각 측정값에 고유한 '토큰 (token)'을 부여하여, 식 내에서 동일한 토큰이 반복되는지 (동일한 관측치 재사용) 아니면 다른 토큰인지 (서로 다른 관측치) 를 구분합니다.
허용 가능한 정의역 (Admissible Domains): 분모가 0 이 되지 않는 등 과학적으로 타당한 환경 (Admissible Environments) 만을 평가 대상으로 제한합니다.

주요 구성 요소:

표현식 언어: 정수 상수, 측정값 (토큰, 구간, 차원), 그리고 사칙연산으로 구성된 최소한의 언어.
토큰 환경 (Token Environment): 각 토큰에 정확한 유리수 값을 할당하는 함수.
**보장된 포락선 (Warranted Enclosure, $Encl(e) $):** 모든 토큰 일관성 환경에서 식$ e$가 취할 수 있는 값들의 집합.
**정의된 포락선 (Defined Enclosure, $DefinedEncl(e) $):** 분모가 0 이 아닌 '허용 가능한 환경' ($ AdmDom$) 에서만 계산된 값들의 집합.
재작성 판단 (Rewrite Judgments):
- 포락선 기반: $e \leadsto e'$ (타겟의 포락선이 소스의 포락선 안에 포함됨).
- 도메인 인식 (Domain-aware): $e \leadsto_d e'$ (소스가 정의된 모든 환경에서 타겟도 정의되어야 하며, 값이 소스의 정의된 포락선 내에 있어야 함).
- 지원 상대적 (Support-relative): 특정 환경 집합 (Support) 에 국한된 재작성 판단.

3. 주요 기여 (Key Contributions)

토큰 민감 포락선 의미론 (Token-sensitive Enclosure Semantics):
- 측정값의 기원 (토큰 동일성) 을 추적하여 재작성의 타당성을 판단하는 의미론을 정립했습니다.
- $e \leadsto e'$ (일방향) 와 $e \rightleftharpoons e'$ (상호 교환 가능) 판단을 제공합니다.
도메인 인식 재작성 판단 (Domain-aware Rewrite Judgments):
- 정의역 (Definedness) 을 고려한 재작성 규칙을 도입했습니다. 특히 $e \leadsto_d e'$ 는 타겟 식이 소스 식이 정의된 모든 환경에서 정의되어야 함을 요구합니다.
- 이는 특이점 제거는 안전하지만, 특이점 도입은 위험함을 형식적으로 증명합니다.
축소 및 회복 정리 (Reduction and Recovery Theorems):
- 축소 정리: 모든 식이 보편적으로 허용 가능한 (universally admissible, 예: 분모가 0 이 될 수 없는 경우) 환경에서 정의될 때, 도메인 인식 계층이 기존 포락선 기반 계층으로 축소됨을 증명했습니다.
- 회복 정리: 양의 구간 (Positive Interval) 자기 나눗셈 ( $x/x = 1$ ) 이나 배경 뺄셈과 같은 긍정적 (Positive) 재작성 규칙들이 지원 상대적 계층 내에서 어떻게 통합되는지 보여줍니다.
엄격한 부정적 결과 (Strict Negative Results):
- Strictness: 도달 가능한 특이점이 존재하면 단순화는 일방향 (One-way) 만 가능합니다.
- 비전파성 (Non-transitivity): 도메인 안전 재작성은 일반적으로 전이적 (Transitive)이지 않습니다. 즉, $A \leadsto_d B$ 이고 $B \leadsto_d C$ 라고 해서 $A \leadsto_d C$ 가 성립하지 않을 수 있으며, 각 단계마다 재검증이 필요합니다.
- 불충분성 정리 (Insufficiency Theorem): 토큰 정체성을 지우거나 정의역만 고려하는 것만으로는 재작성 클래스를 구분할 수 없음을 증명했습니다. 기원과 정의역은 모두 필수적입니다.
Lean 4 를 통한 형식화:
- 모든 정의와 정리 (약 2,700 줄의 Lean 4 코드, 143 개의 정리, 45 개의 정의) 가 sorry 없이 완전히 증명되었습니다.

4. 주요 결과 및 사례 (Results & Examples)

기원에 따른 분류:
- $Meas(t) - Meas(t) \rightleftharpoons 0$ : 동일 토큰이므로 교환 가능.
- $Meas(t_1) - Meas(t_2) \leadsto 0$ (일방향): 서로 다른 토큰이므로 0 이 될 수는 있지만, 항상 0 은 아님.
정의역에 따른 분류:
- $Meas(t, [0.1, 1])/Meas(t, [0.1, 1]) \rightleftharpoons 1$ : 분모가 0 이 될 수 없으므로 교환 가능.
- $Meas(t, [0, 1])/Meas(t, [0, 1]) \leadsto 1$ (일방향): $t=0$ 일 때 특이점이 존재하므로, 1 로 단순화하는 것은 안전하지만 역은 불가능.
비교 불가능한 정의역:
- $x/x$ 와 $(x-1)/(x-1)$ 은 공통 정의역 ( $x \neq 0, 1$ ) 에서는 모두 1 이지만, 서로의 정의역 ( $x=0$ 또는 $x=1$ ) 을 포함하지 않아 어느 쪽도 다른 쪽으로 대체할 수 없습니다.

5. 의의 (Significance)

이 논문은 과학적 계산 및 형식적 검증 분야에서 다음과 같은 중요한 통찰을 제공합니다.

수학적 등식의 한계 명확화: 측정 데이터를 다룰 때 대수적 등식만으로는 재작성의 안전성을 보장할 수 없으며, **기원 (Provenance)**과 **정의역 (Definedness)**을 동시에 고려해야 함을 증명했습니다.
안전한 자동화 기초: 과학적 시뮬레이션, 신호 처리, 데이터 분석 파이프라인에서 자동화된 식 단순화 (Symbolic Optimization) 를 수행할 때, 단순한 대수적 규칙 적용이 아니라 토큰 추적과 정의역 검사가 필수적임을 보여줍니다.
형식적 검증의 표준: Lean 4 를 통해 모든 논리를 기계적으로 검증함으로써, 복잡한 조건부 재작성 규칙의 오류 가능성을 제거하고 신뢰할 수 있는 이론적 기반을 마련했습니다.
기존 연구와의 차별화: 기존 구간 산술 (Interval Arithmetic) 이 '포락선의 정확도'에 집중했다면, 이 논문은 '재작성의 타당성 (Rewrite Classification)'에 초점을 맞추어 새로운 차원의 문제를 해결했습니다.

결론적으로, 이 연구는 측정 기반 표현식의 안전한 재작성을 위해 토큰 기반의 의존성 추적과 부분 함수의 정의역 관리가 결합된 통합 프레임워크가 필요함을 제시하며, 이를 형식적으로 검증한 최초의 체계적인 작업 중 하나입니다.