괴델 부호화

읽기 전에 이 문서는 영어 위키백과의 Gödel numbering 문서의 "2021년 11월 8일 18시 34분" 버전을 참조하였습니다.

1. 개요[편집]

---

괴델 부호화는 논리식에 각 기호를 숫자로 매칭시키는 것을 말한다. 쿠르트 괴델이 괴델의 불완전성 정리를 증명하기 위해 각각의 논리식은 자연수에 일대일 대응시키기 위에 사용하였다. 각 부호에 1, 2, 3, ... 등의 자연수를 대응하고, 식의 위치에 2, 3, 5, ... 등의 소수를 대응시켜 소인수 분해를 이용해 pos1^sign1pos2^sign2...의 자연수에 논리식을 대응한다. 예를 들어, 1이 1, 2가 2, +가 3, =이 4의 값을 갖는다면, 1+1=2에 대응되는 자연수는 2¹3³5¹7⁴11² = 78440670가 된다.

2. 예시[편집]

---

소인수분해에 기반한 방법을 사용하며, 논리식을 위 표로 치환한 집합 [math(\{ x_1,x_2,x_3,...,x_n \})]에 대하여 논리식에 부호화된 값 [math(enc(x_1,x_2,x_3,...,x_n))]를 [math(enc(x_1,x_2,x_3,...,x_n)=2^{x_1} \cdot 3^{x_2} \cdot 5^{x_3} \cdot \cdot \cdot {p_n}^{x_n})]로 치환하는 형식이다.

예를 들면, Nagel과 Newman이 사용한 괴델 부호화에서 기호 "0"에 대한 괴델 수는 6이고 기호 "="에 대한 괴델 수는 5이다. 따라서 그들의 체계에서 공식 "0"의 괴델 수는 0"은 [math(2^6)] × [math(3^5)] × [math(5^6)] = 243,000,000이다.