자기 수정 하에서의 라이스 정리: 고양 연산자와 정규형
Rice's Theorem under Self-Modification: Elevation Operators and a Normal Form
한국어 초록
우리는 자기 수정(self-modifying) 계산 시스템이 안전성 속성을 다음 단계에서 보존하는지(보존, preservation), 그리고 전체 진화 과정에 걸쳐 보존하는지(지속, persistence)를 알고리즘적으로 인증할 수 있는지를 묻는다. 자기 수정의 한 단계는 프로그램 인덱스에 대한 전체 계산 가능 변환 $\Phi$이며, 보존은 고양된(elevated) 속성 $\Lambda_\Phi(P)=\{x\in P:\Phi(x)\in P\}$로 표현된다. $\Phi$가 외연적(extensional)이면 $\Lambda_\Phi(P)$는 행동적(behavioural) 속성이 되어 라이스 정리가 적용된다. $\Phi$가 코드를 읽는 경우 $\Lambda_\Phi(P)$는 더 이상 행동적이지 않지만, 균일 교란(uniform disruption, $K$를 인코딩하는 비활성 래퍼) 하에서는 라이스 정리를 증명하는 s-m-n 환원이 단일한 행동적 파이버(fibre) 내부에서 작동하며, $\Lambda_\Phi(P)$는 정지 문제의 차수(halting degree)를 물려받는다. 이는 두 가지 스케일에서 나타나는 라이스 정리의 하나의 풀백(pullback)이다. 한 단계의 차수는 $P$의 차수를 넘지 않으며, 지속은 $\Phi$가 외연적인 경우에도 $\Sigma^0_1$ 속성에 대해 $\Pi^0_2$-완전(complete)일 수 있다. 이어서 우리는 재작성(rewriting), 감독(supervision), 시스템 비교에 공통된 메커니즘을 분리해 내는데, 이것이 의미론적 고양 연산자(semantic elevation operator)이다. 이 연산자는 기저 시스템을 감싸고, $K$에 고정된 하나의 유한한 사건, 즉 속성으로의 진입 또는 이탈에 반응한다. 이 부류에서 고양된 속성은 트리거와 극성(polarity)만으로 결정되는 $P\cap S_a$ 또는 $P\setminus S_a$이며, $K$ 또는 그 여집합을 물려받고, 안전 영역은 재귀적으로 열거 가능하지 않다. 라이스-샤피로(Rice-Shapiro) 정리는 극성을 제한한다. 즉 유한 트리거는 $\Sigma^0_1$ 속성에만 진입할 수 있고 $\Pi^0_1$ 속성에서만 이탈할 수 있다. 네 가지 축(기능적, 연역적, 참조 대상에 대한 적합성, 모니터링)은 검증된 사례이며, 감독자의 탑(tower)을 쌓아도 이 장벽은 낮아지지 않는다. 또한 이 부류 밖에 있는 $K$-난해(K-hard) 내포적(intensional) 연산자를 제시하고, 미해결 특성화 문제를 명시한다.
원문 초록
We ask whether it can be certified algorithmically that a self-modifying computational system preserves a safety property at its next step (preservation) and along its whole evolution (persistence). One step of self-modification is a total computable transformation $\Phi$ of program indices, and preservation is the elevated property $\Lambda_\Phi(P)=\{x\in P:\Phi(x)\in P\}$. When $\Phi$ is extensional, $\Lambda_\Phi(P)$ is behavioural and Rice's theorem applies. When $\Phi$ reads the code, $\Lambda_\Phi(P)$ is no longer behavioural, yet under uniform disruption (an inert wrapper encoding $K$) the s-m-n reduction that proves Rice's theorem works inside a single behavioural fibre, and $\Lambda_\Phi(P)$ inherits the halting degree: one pullback of Rice, at two scales. One step never exceeds the degree of $P$; persistence can be $\Pi^0_2$-complete for $\Sigma^0_1$ properties, even for extensional $\Phi$. We then isolate the mechanism shared by rewriting, supervision and system comparison: the semantic elevation operator, which wraps a base system and reacts to one finite event anchored to $K$, entering or leaving the property. For this class the elevated property is $P\cap S_a$ or $P\setminus S_a$, determined by trigger and polarity alone; it inherits $K$ or its complement; and the safe region is not recursively enumerable. The Rice-Shapiro theorem restricts the polarity: a finite trigger can only enter a $\Sigma^0_1$ property and only leave a $\Pi^0_1$ one. Four axes (functional, deductive, conformance to a reference, monitoring) are verified instances, and towers of supervisors do not lower the barrier. We exhibit $K$-hard intensional operators outside the class and state the open characterisation problem.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.11326v2제출 시각 미확인
- arXiv:2609.11326v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
자기 개선 에이전트의 상대적 계산가능성 이론
A Relative-Computability Theory of Self-Improving Agents
토론
이 논문과 연결된 포럼 글이 아직 없습니다.