괴델 기계

**괴델 기계** 또는 **괴델 머신**(Gödel machine)은 최적의 방식으로 문제를 해결하는 가상의 자기 개선 컴퓨터 프로그램이다. 이 기계는 새로운 코드가 더 나은 전략을 제공한다는 것을 증명할 수 있을 때 자체 코드를 다시 작성하는 재귀적 자기 개선 프로토콜을 사용한다. 이 기계는 위르겐 슈미트후버가 발명했지만(2003년에 처음 제안됨), 수학 이론에 영감을 준 쿠르트 괴델의 이름을 따서 명명되었다.

괴델 기계는 "학습을 통한 학습"이라고도 알려진 메타 학습 문제를 다룰 때 자주 논의된다. 응용 분야로는 인간의 설계 결정을 자동화하고 여러 관련 작업 간의 지식 이전이 있으며, 보다 견고하고 일반적인 학습 아키텍처 설계를 이끌어낼 수 있다. 이론적으로는 가능하지만, 완전한 구현은 아직 만들어지지 않았다.

괴델 기계는 마르쿠스 후터의 AIXI와 자주 비교되는데, AIXI는 인공 일반 지능에 대한 또 다른 형식 사양이다. 슈미트후버는 괴델 기계가 AIXItl을 초기 하위 프로그램으로 구현한 다음, 검색 코드에 대한 다른 알고리즘이 더 좋다는 증거를 찾으면 스스로 수정할 수 있다고 지적한다.

## 제한 사항

컴퓨터가 해결하는 전통적인 문제는 하나의 입력만을 요구하고 일부 출력을 제공한다. 이러한 종류의 컴퓨터는 초기 알고리즘이 하드웨어에 고정되어 있었다. 이는 동적인 자연 환경을 고려하지 않으므로, 괴델 기계가 극복해야 할 목표였다.

그러나 괴델 기계는 자체적인 한계를 가지고 있다. 괴델의 제1 불완전성 정리에 따르면, 산술을 포함하는 모든 형식 시스템은 결함이 있거나 시스템 내에서 증명할 수 없는 명제를 허용한다. 따라서 무한한 계산 자원을 가진 괴델 기계조차도 그 효과를 증명할 수 없는 자기 개선 사항을 무시해야 한다.

## 관심 변수

괴델 기계의 실행 시간에 특히 유용한 세 가지 변수가 있다.

* 어떤 시간 t에서 변수 \text{time}은 t의 이진수 값을 갖는다. 이 값은 기계의 실행 시간 내내 꾸준히 증가한다.

* 자연 환경에서 괴델 기계로 들어오는 모든 입력은 변수 x에 저장된다. x는 변수 \text{time}의 다른 값에 대해 다른 값을 가질 가능성이 높다.

* 괴델 기계의 출력은 변수 y에 저장되며, 여기서 y(t)는 어떤 시간 t에서의 출력 비트열이 된다.

어떤 주어진 시간 t ((1 \leq t \leq T))에서 목표는 미래의 성공 또는 유용성을 극대화하는 것이다. 일반적인 유틸리티 함수는 다음 패턴을 따른다 u(s, \mathrm{Env}) : S \times E \rightarrow \mathbb{R}:

: u(s, \mathrm{Env}) = E_\mu \Bigg[ \sum_{\tau=\text{time}}^T r(\tau) \mid s, \mathrm{Env} \Bigg]

여기서 r(t)는 시간 t에서의 실수 값 보상 입력(s(t) 내에 인코딩됨)이고, E_\mu [ \cdot \mid \cdot ]는 가능한 분포 집합 M의 일부 알려지지 않은 분포 \mu에 대한 조건부 기댓값 연산자를 나타낸다(M은 환경의 가능한 확률적 반응에 대해 알려진 모든 것을 반영함). 그리고 위에 언급된 \text{time} = \operatorname{time}(s)는 현재 주기를 고유하게 식별하는 상태 s의 함수이다. 적절한 행동을 통해 예상 수명을 연장할 가능성을 고려한다.

## 증명 기법에 사용되는 명령어

아래 6가지 증명 수정 명령어의 특성으로 인해 잘못된 정리를 증명에 삽입하는 것이 불가능하며, 따라서 증명 검증을 사소하게 만든다.

### get-axiom(n)

n번째 공리를 현재 정리 시퀀스에 정리로 추가한다. 아래는 초기 공리 체계이다.

* **하드웨어 공리**는 기계의 구성 요소가 한 주기에서 다음 주기로 어떻게 변할 수 있는지를 공식적으로 지정한다.
* **보상 공리**는 하드웨어 명령어의 계산 비용과 출력 동작의 물리적 비용을 정의한다. 관련 공리는 또한 괴델 기계의 수명을 모든 보상/비용을 나타내는 스칼라량으로 정의한다.
* **환경 공리**는 이전 입력 y 시퀀스를 기반으로 환경에서 새로운 입력 x가 생성되는 방식을 제한한다.
* **불확실성 공리/문자열 조작 공리**는 산술, 미적분, 확률론, 문자열 조작에 대한 표준 공리로, 괴델 기계 내에서 미래 변수 값과 관련된 증명을 구성할 수 있도록 한다.
* **초기 상태 공리**는 초기 상태의 일부 또는 전부를 재구성하는 방법에 대한 정보를 포함한다.
* **유틸리티 공리**는 유틸리티 함수 u의 형태로 전체 목표를 설명한다.

### apply-rule(k, m, n)

추론 규칙(예: 후건 부정, 전건 긍정)의 인덱스 k를 받아 이전에 증명된 두 정리 m과 n에 적용을 시도한다. 결과로 얻은 정리는 증명에 추가된다.

### delete-theorem(m)

현재 증명에서 인덱스 m에 저장된 정리를 삭제한다. 이는 중복되고 불필요한 정리로 인한 저장 제약을 완화하는 데 도움이 된다. 삭제된 정리는 위 **apply-rule** 함수에서 더 이상 참조할 수 없다.

### set-switchprog(m, n)

S p의 비어 있지 않은 서브스트링인 경우 switchprog S pm:n을 대체한다.

### check()

증명 검색의 목표가 달성되었는지 확인한다. 대상 정리는 현재 공리화된 유틸리티 함수 u(항목 1f)가 주어졌을 때, p에서 현재 switchprog로 전환하는 유틸리티가 p의 실행을 계속하는 유틸리티보다 높을 것임을 명시한다(이는 대안 switchprog를 계속 검색할 것이다).

### state2theorem(m, n)

두 인자 m과 n을 받아 Sm:n의 내용을 정리로 변환을 시도한다.

## 적용 예시

### 시간 제한 NP-난해 최적화

괴델 기계에 대한 초기 입력은 다양한 길이의 모서리로 연결된 수많은 노드를 가진 연결된 그래프의 표현이다. 주어진 시간 T 내에 모든 노드를 연결하는 순환 경로를 찾아야 한다. 유일한 실수 값 보상은 시간 T에 발생한다. 이 보상은 지금까지 찾은 최적 경로 길이로 나눈 1과 같다(찾지 못한 경우 0). 다른 입력은 없다. 예상 보상을 최대화하는 부수적인 효과는 초기 편향이 주어진 상태에서 제한된 시간 내에 찾을 수 있는 최단 경로를 찾는 것이다.

### 빠른 정리 증명

2보다 큰 모든 짝수가 두 소수의 합이라는 것을 가능한 한 빨리 증명하거나 반증한다(골드바흐의 추측). 보상은 t분의 1이며, t는 첫 번째 증명을 생성하고 확인하는 데 필요한 시간이다.

### 제한된 자원으로 예상 보상 극대화

시간당 최소 1 리터의 휘발유가 필요한 인지 로봇이 부분적으로 알려지지 않은 환경과 상호 작용하며, 숨겨진 한정된 휘발유 저장고를 찾아 가끔 탱크를 다시 채우려고 한다. 로봇은 수명에 비례하여 보상을 받으며, 최대 100년 후에 또는 탱크가 비거나 절벽에서 떨어지는 등의 상황에서 사망한다. 확률적 환경 반응은 처음에는 알려지지 않았지만, 계산하기 어려운 환경 반응은 가능성이 낮다는 스피드 사전에 따라 공리화된 스피드 사전에서 샘플링된 것으로 가정된다. 이는 거의 최적에 가까운 예측을 위한 계산 가능한 전략을 허용한다. 예상 보상을 극대화하는 부수적인 효과는 예상 수명을 극대화하는 것이다.

## 같이 보기
* 괴델의 불완전성 정리

## 각주

## 외부 링크
* 괴델 기계 홈페이지

분류:인공지능