🔢 mathematics

Inexpressibility in Exp-Minus-Log

본 논문은 초등 함수를 상수와 단일 2 자리 연산으로 축소하는 Exp-Minus-Log 체계가 계산 가능한 수만을 표현할 수 있음을 규명함으로써, Chaitin 의 $\Omega_U$ 가 이 체계 내에서는 표현 불가능함을 증명한다.

원저자: Mark Carney

게시일 2026-05-05

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Mark Carney

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

마법처럼 모든 것을 할 수 있는 주방이 있다고 상상해 보세요. 이 주방에는 블렌더, 오븐, 믹서와 같은 완전한 도구 세트가 있는 것이 아니라, 오직 하나의 특별한 도구, 즉 '마법 지팡이'(논문에서는 E로 표기됨) 와 하나의 재료인 숫자 1만 있습니다.

마크 카니의 논문은 오직 이 지팡이 하나와 그 한 가지 재료만을 사용하여 가능한 모든 숫자를 '요리'해 보려고 할 때 어떤 일이 일어나는지 탐구합니다.

마법 지팡이의 레시피

지팡이는 매우 특정한 방식으로 작동합니다. 만약 당신이 A와 B라는 두 가지 물체를 가리킨다면, 지팡이는 특정한 마법을 부립니다. 즉, A 의 지수함수 (매우 빠르게 성장시키는 정교한 방법) 를 취하고 B 의 로그함수 (축소시키는 방법) 를 뺍니다.

공식: 결과 = exp(A) - log(B)

원래 연구자들 (Odrzywo lek) 은 이 하나의 마법과 숫자 1 만으로도 우리가 일반적으로 '표준 수학'으로 생각하는 거의 모든 것을 실제로 재현할 수 있음을 보여주었습니다. 정수, 분수, 숫자 $\pi$ , $e$ , 그리고 사인과 코사인 같은 복잡한 함수까지 만들어낼 수 있습니다. 마치 숟가락 하나와 밀가루 한 컵만으로 전체 웨딩 케이크를 구울 수 있는 것과 같습니다.

큰 질문: 모든 것을 '요리'할 수 있을까요?

논문의 질문은 더 깊어집니다: 이 주방이 '만들 수 없는' 것이 있을까요?

이 질문에 답하기 위해 저자는 이 '마법 지팡이' 주방을 EL 숫자(수학자 티모시 차우의 이름을 딴) 라는 알려진 숫자 집합과 비교합니다. 논문은 마법 지팡이 주방과 차우의 주방이 실제로 같은 장소임을 증명합니다. 그들은 정확히 같은 숫자 목록을 만들어낼 수 있습니다.

'요리할 수 없는' 재료: 차이틴의 $\Omega$

그런 다음 저자는 차이틴의 $\Omega$ (오메가) 라는 매우 기이하고 이론적인 재료를 소개합니다.

그것은 무엇인가요? 컴퓨터 프로그램이 정지 (halting) 하거나 영원히 실행될 확률을 나타내는 숫자를 상상해 보세요.
왜 특별한가요? 이 숫자는 '비계산적'입니다. 아직 계산되지 않은 숫자가 아니라, 어떤 컴퓨터 (얼마나 강력하든) 도 그 정확한 숫자를 적어내거나 다음 숫자를 예측하는 것이 수학적으로 불가능한 숫자입니다. 그것은 존재하지만, 단계별 레시피로는 근본적으로 '접근할 수 없는' 숫자입니다.

주요 발견

논문의 핵심은 단순하지만 강력한 규칙을 증명합니다: 마법 지팡이로 만들 수 있는 모든 숫자는 '계산 가능'합니다.

이를 쉬운 영어로 논리적으로 설명하면 다음과 같습니다:

재료는 안전합니다: 계산하기 쉬운 숫자 1 로 시작합니다.
과정은 안전합니다: 마법 지팡이는 exp와 log 두 가지 일만 수행합니다. 논문은 컴퓨터가 계산할 수 있는 숫자를 이 도구들에 입력하면, 컴퓨터도 계산할 수 있는 결과를 내놓는다는 것을 보여줍니다.
결론: 계산 가능한 숫자로 시작하고 계산 가능한 도구만 사용하므로, 이 시스템에서 만들 수 있는 모든 숫자는 계산 가능해야 합니다.

차이틴의 $\Omega$ 는 계산 가능하지 않기 때문에, 이 주방에서는 그것을 만들 수 없습니다.

최종 판결

논문의 결론은 '형식적 비표현 정리'입니다. 간단히 말해:

마법 지팡이 주방은 $\pi$ , $e$ , 그리고 공학과 물리학에서 사용되는 모든 숫자를 포함한 방대하고 무한한 숫자 목록을 만들어낼 수 있습니다.
그러나, 주방이 결코 건드릴 수 없는 광활한 숫자의 바다가 존재합니다.
차이틴의 $\Omega$ 는 이러한 접근 불가능한 숫자들의 '대표 주자'입니다. 이는 특정 규칙 체계로는 표현할 수 없는 수학적 진리가 존재한다는 구체적인 증명입니다.

간단한 비유

마법 지팡이 시스템을 빨간 벽돌만 있는 레고 세트라고 생각하세요.

당신은 집, 자동차, 성, 또는 우주선을 만들 수 있습니다 (이것들은 $\pi$ 와 $e$ 와 같은 '계산 가능한' 숫자들입니다).
하지만 누군가 당신에게 파란 벽돌을 만들어달라고 요청하면, 당신은 할 수 없습니다. 빨간 벽돌을 아무리 많이 쌓아도 파란 벽돌을 만들어낼 수 없습니다.
차이틴의 $\Omega$ 는 바로 그 '파란 벽돌'입니다. 그것은 수학의 우주에 존재하지만, 당신에게 제공된 빨간 벽돌 (EML 시스템) 로는 결코 구성할 수 없는 재료 (비계산성) 로 만들어져 있습니다.

요약하자면: 이 논문은 단일 함수 시스템이 일상생활과 과학에서 우리가 사용하는 거의 모든 숫자를 포괄할 정도로 놀라울 정도로 강력하다는 것을 확인시켜 주지만, 한 가지 확실한 한계가 있음을 보여줍니다. 그것은 '비계산적' 숫자에 도달할 수 없으며, 이는 어떤 수학적 개념들이 이 특정 방식으로 기록하는 것에는 영원히 도달할 수 없음을 증명합니다.

기술적 요약: Exp-Minus-Log 의 비표현성

문제 제기
본 논문은 Odrzywo lek [4] 에 의해 원래 정의된 Exp-Minus-Log(EML) 시스템에 대한 이론적 이해의 공백을 다루고 있다. 이 시스템은 복소수 위의 모든 기본 함수, 상수, 연산을 단일 이항 연산자 $E(\alpha, \beta) = \exp(\alpha) - \log(\beta)$ 와 상수 '1'로 축소한다. Odrzywo lek 의 작업은 주로 구성적이며 실존적이었으며, 즉 표준 기본 함수를 어떻게 표현할 수 있는지 보여주었지만, 형식적인 비표현성 정리를 확립하지는 않았다. 구체적으로, EML 시스템이 비계산적 실수를 표현할 수 있는지 여부는 여전히 열린 질문으로 남아 있었다. 본 논문은 시스템 내에서 표현 가능한 모든 수의 계산 가능성 상태를 결정함으로써 EML 표현성의 한계를 규명하고자 한다.

방법론
저자들은 EML 의 경계를 확립하기 위해 형식 논리, 계산 가능한 분석, 알고리즘 정보 이론을 결합하여 사용한다. 방법론은 세 가지 논리적 단계로 진행된다:

형식적 동등성: 논문은 먼저 Odrzywo lek 의 EML 수와 Chow 의 EL 수 [2] 사이의 엄밀한 동등성을 확립한다. 명시적인 구문 치환을 제공함으로써, 저자들은 EML 수의 체가 $\exp$ 와 $\log$ 에 대해 닫혀 있는 $\mathbb{C}$ 의 가장 작은 부분체인 EL 수의 체와 동일함을 보여준다.
계산 가능성 분석: 계산 가능한 분석의 결과 (특히 [7] 와 [6]) 를 활용하여 저자들은 관련 연산들의 계산 가능성을 분석한다. 그들은 지수 함수가 모든 계산 가능한 복소수 입력에 대해 계산 가능하다는 사실을 이용한다. 로그의 경우, 가지 절단 (branch cut) 문제를 해결하기 위해 정의된 모든 EML 표현식에 대해 로그의 인자가 음의 실수 축 위에 있거나 (이 경우 크기와 $\pi$ 를 통해 값이 계산 가능함), 유리수 거리만큼 가지 절단으로부터 떨어져 있음을 증명한다.
계산 가능성의 귀납적 증명: EML 표현식의 구문에 대한 구조적 귀납을 사용하여, 저자들은 정의된 모든 EML 표현식이 계산 가능한 복소수로 평가됨을 증명한다.
증거 선택: 비표현성을 입증하기 위해 논문은 범용 프리픽스-프리 튜링 머신의 정지 확률인 Chaitin 의 $\Omega_U$ 를 표준적인 증거로 활용한다. $\Omega_U$ 는 왼쪽-계산 가능 열거 가능하지만 비계산적인 것으로 알려져 있다.

주요 기여 및 결과
본 논문은 다음과 같은 주요 결과를 도출한다:

동등성 정리: EML-표현 가능한 수의 집합이 정확히 Chow 의 EL 수의 집합임을 증명한다 ($EML = EL$).
계산 가능성 정리: 논문은 모든 EML-표현 가능한 수가 계산 가능함을 증명한다. 구체적으로, 값이 정의된 임의의 닫힌 EML 표현식 $\phi$ 에 대하여 $[[\phi]]$ 는 계산 가능한 복소수이다. 결과적으로, EML-구성 가능한 실수의 집합 ( $EML_{\mathbb{R}}$ ) 은 계산 가능한 실수의 집합 ( $\text{Comp}_{\mathbb{R}}$ ) 의 부분집합이다.
비표현성 정리: EML 수의 계산 가능성과 Chaitin 의 $\Omega_U$ 의 비계산성을 결합함으로써, 논문은 $\Omega_U \notin EML_{\mathbb{R}}$ 임을 형식적으로 증명한다.
측도론적 함의: EML 수의 집합이 구문 (syntax) 의 가산성으로 인해 가산집합이므로, 비 EML-표현 가능한 실수의 집합은 $\mathbb{R}$ 에서 완전한 르베그 측도 (full Lebesgue measure) 를 가진다. 여기에는 $\Omega_U$ 뿐만 아니라 정지 집합의 이진 전개, Specker 수열의 극한, Martin-Löf 무작위 실수 등 다른 클래스의 비계산 수들도 포함된다.

의의 및 주장
본 논문은 EML 시스템에 대한 형식적인 비표현성 정리를 제공함으로써 Odrzywo lek 의 원래 작업이 남긴 특정 이론적 공백을 메운다고 주장한다. 그 의의는 EML 시스템을 기본 함수를 생성하는 도구로만 보는 것이 아니라, 계산 가능성에 의해 엄격하게 제한된 시스템으로 규명하는 데 있다.

저자들은 결과를 겸손하게 형식적인 한계로 제시한다. 즉, EML 은 미적으로 매력적이며 기호 계산 및 정확한 산술 (서론에서 CAS 시스템과 관련하여 언급됨) 에 유용하지만, "표준적인" 비계산 실수를 표현할 수는 없다는 것이다. 본 논문은 새로운 응용이나 실험적 제안을 제시하지 않으며, 오히려 $EML_{\mathbb{R}} \subsetneq \mathbb{R}$ 이며 더 구체적으로는 $EML_{\mathbb{R}} \subseteq \text{Comp}_{\mathbb{R}}$ 임을 확립하는 기초적인 증명으로서의 역할을 한다. 이 결과는 단일 연산자를 통해 표현 가능한 "닫힌 형식"의 수들이 계산 가능한 수의 영역으로 엄격히 제한됨을 확인시켜 준다.