https://blog.naver.com/wnstkd1928/223277502000
언젠간 번역퀄이 나아지길 바라면서 조금씩 공부 중입니다.
pdf로 100쪽 가량 읽은 소감으로는 페아노 산술이 아닌 더 약한 산술내에서 완전성이 증명되는 등, 혼자 공부하는 상황이라 약간 외롭긴 하지만, 이 책엔 다소 재밌는 내용들이 많습니다.
3.3. Effectuve eumerability, 효과적 열거가능성)
a) 비-공집합인 집합 Σ가 열거가능하다는 것은 자연수 집합과 ∑사이 어떠한 surjection function f : |N ->Σ가 존재한다는 것인데, 이는 집합 Σ를 열거하는 것이다.
이전에 우리가 주목했듯, 이 정의는 열거하는 함수가 계산적이라는 것을 요구하지 않는다. 즉, 여기서 열거하는 함수 f는 Σ의 원소와 수 사이의 임의의 연관관계인 것이다. 이는 심지어 유한하게 구체화되는 것을 요하지 않는다. 이와 대조하여, 우리는 다음과 같이 말할 수 있다.
집합 Σ가 효과적으로 열거가능하다(effectively enumerable, 이하, e.e.) iff Σ가 공집합이거나 혹은 Σ 의 원소를 열거할 수 있는 효과적으로 계산가능한 함수가 존재한다.
(각주-효과적으로 열거적이거나 열거적이만 효과적이지 않다는 것은 이 두 경우 전부 어떠한 함수인지에 대해 의존하지 않고, 우리가 그것에 대해 아는 함수인가에 의존하지 않는다. 물론 여기서의 전문용어들은 전체적으로 안정적이지 않다 : 어떤 저자는 열거가능성을 효과적으로 열거가능하다는 의미로 사용하며, 가산적(denumerable)이란 의미를 넓은 의미에서의 열거가능성을 의미하는 것으로 누군가는 사용하기도 한다)
b) e.e.무한 집합의 사소한 예시에 대해, 계산가능한 함수 f(n)=n2 는 완전제곱수인 자연수를 효율적으로 열거가능하다. 또한 소수인지에 대해 결정하는 잘-알려진 테스트를 적용하고, 이를 연속적으로 리스트를 작성하면 : 이러한 절차는 절대 끝나지 않는 목록을 발생시키지만, 이 목록에는 모든 소수가 마침내 나타날 것이기에, 그래서 소수들은 효과적으로 열거가능하다.
theorem 3.3. 만일 Σ가 수들의 효과적으로 결정가능한(effectvely decidable) 집합이라면, 이것은 효과적으로 열거가능하다.
pf) Σ가 공집합인 경우 자명하다. 따라서 s in Σ라 하자. 그리고 임의의 input n에 대해 n in Σ인지의 여부를 효과적으로(effectively) 테스트하는 알고리즘을 고려하자(이는 효과적으로 결정가능한 집합이라는 가정하 가능하다).
그리고 알고리즘에 대해 'yes'의 output을 n으로 두고 그렇지 않으면, s로 두자. 이러한 알고리즘은 surjection function f : |N ->Σ 를 계산한다. 그래서 Σ는 효과적으로 열거가능하다.Q.E.D.
c) 이것의 역은 가능한가? 즉, 만일 효과적으로 가 이것은 효과적으로 결정가능해야만 하는가?
직관적으로 이는 일반화되진 않는다. 만일 우리에게 오직 계산적인 열거하는 함수 f : |N-> Σ가 주어진다면, 우리는 f(0), f(1), f(2),...를 계산하는 것을 시작할 수 있어보인다. 만일 마침내 어떤 n에 대해 f(n)=s인 n을 찾게 된다면, 이 때 s in Σ인 것으로 결정하면 된다. 그러나 만일 그러한 n을 찾지 못했다면, 모든 것이 여전히 진행될 것이고, 아마도 우리가 충분히 길게 보지 않았기 때문에 s in Σ거나 s not in Σ일 것으로 여진히 판명될 것이다.
하지만 f(n)에 대한 유한한 긴 탐색은 아무리 길어도 아무것도 해결할 수 없을 수도 있다 :
theorem 3.4. 만일 Σ와 이것의 여집합 Σ*가 둘다 효과적으로 열거가능한 수들의 집합이라면, Σ는 효과적으로 결정가능하다.
pf) Σ가 효과적으로 계산가능한 함수 f에 의해 열거된다고 가정하자, 그리고 여집합 Σ는 g에 의해 가능하다고 하자. f(0),g(0),f(1),g(1),....의 경우 처럼 계산한다면, 마침내 우리는 output 값 s에 대해 얻을 수 있다. 왜냐하면 s는 Σ나 이것의 여집합에 속해야만 하기 때문이다. 만일 f(m)=s인 m을 얻게 된다면, 이 알고리즘은 s in Σ라는 판결을 우리에게 준다. 그리고 만일 g(n)=s인 n을 얻는다면 s가 Σ에 속한다고 알고리즘은 우리에게 알려준다.Q.E.D
우리는 여기서 우리의 원리 안에서의 결정가능성(decidability-in-principle)에 대한 매우 관대한(ultra-generous) 개념에 의존한다. 우리는 s가 Σ에 속하는지의 여부를 보기 위한 막대한 시간동안 우리의 손을 꼬고 있을 수도 있다. 그러나 '기다리고 보는' 방법은 유한한 시간 내에서 결과를 생산하기 위한 우리의 가정에 의해, 전적으로 기계적인 방식 내에서 이뤄짐에 의해 보장이 된다. 그래서 이것은 공식적으로 관대하다는 의미에서의 효과적 절차로써 간주할 수 있다.
그래서 만일 수에 관한 모든 e.e set이 효과적으로 열거가능한 여집합을 가진다면, 수에 대한 모든 e.e. set은 전적으로 결정가능한 것이 되는데, 이는 이는 위에서의 우리의 직관적인 생각과는 대조된다. 그러나 3.5 section에서 볼 것인데, 어떠한 e.e. 집합들은 효과적으로 열거할 수 없는 여집합을 가지며, 그리고 실제로 수에 대한 비결정적인 e.e.집합도 존재한다.
3.4. Another way of defining effective enumerable set of numbers
이 장에서는 수에 관한 e.e. 집합을 특징화(characterizing) 하는 대안적인 방법을 소개할 것이다.
a) 1항 total numerical function f : |N -> |N 이 효과적으로 계산가능하다면, 우리는 알고리즘 절차 Π이 존재한다고 말할 것인데, 이는 input으로써의 주어진 수에 대해 그것의 값을 계산하는데 이용되는 것이다. 그러나 역시, 모든 알고리즘 Π이 total numerical 1항 함수를 계산할 수 있는 것은 아니다. 다른 알고리즘은 몇몇 인풋으로써의 수들에 대해 산출값을 건내긴 하지만, 그것이 아닌 다른 것에선 적용되지 않는 알고리즘도 있다(가령, partial function을 계산하는 것을 예로 들 수 있다). 혹은 많은 알고리즘들이 우리가 인풋으로써의 수를 투입할 때, 알고리즘의 순환 속에서 막히는 경우도 존재한다. 이에 따른 정의 하나를 소개한다 :
알고리즘 Π에 대한 수치적 정의역(numerical domain)은 자연수 n들에 대한 집합인데, 이는 인풋으로써 수 n에 알고리즘 Π을 적용한다면, 이 알고리즘의 작동이 결국엔 그 원칙 안에서 종료되고 어떠한 수를 산출값으로써 건내는 것이다.
이러한 정의를 이용하여, 어떠한 알고리즘 Π든 간에, 이것의 수치적 정의역은 항상 수에 대한 효과적으로 열거가능한 집합인 것이라는 놀라운 결과를 증명할 것이다. 실제로 이것은 동치인 조건이다 :
theorem 3.5. W가 수에 대한 effectively enumerable(이하 e.e) set iff 이것은 어떤 알고리즘 Π에 대한 numerical domain이다.
pf)
(=>)
W가 e.e set of numbers라 하자. 정의에 따라 W는 (1) 공집합 혹은 ∃ (2) effectively conputable 함수 f s.t. f는 W의 원소를 열거 가능하다(즉, n in W iff ∃i, f(i) = n, f : |N -> W)
(1)의 경우 어떠한 산출값도 반환하지 않는 임의의 알고리즘을 제시한다면, 조건을 만족
(2)의 경우, ∃ algorithm Π s.t. 이 알고리즘은 f를 계산한다.
Π를 이용하여 더 복잡한 새 알고리즘을 구성가능한데, Π+는 다음을 따른다 :
주어진 input으로써의 자연수 n에 대해, f(0),f(1),...의 값을 계산하기 위해 계속 알고리즘 Π을 시행하며, 이러한 시행은 f(i)=n인 i를 찾을 때까지 계속되며, 만일 발견한다면 알고리즘 시행은 멈추고 수 i를 반환한다. 그렇게 된다면 Π+의 수치적 정의역(numerical domin)은 명백히 W가 된다(n in W가 확인되는 때, 알고리즘 Π+은 종료될 것이다).
(<=)
W가 어떤 알고리즘 Π의 numerical domain이라 하자. 이 경우 정리를 증명키 위해 우리가 기본적으로 해야할 것은 알고리즘 Π의 시행을 input 0,1,2 상에 교차로 끼우면서, 몇몇 output값과 함께 알고리즘 Π를 종료시키는 그러한 input들을 다시 내뱉게 하여 W의 효과적인 열거를 우리에게 주도록 하는 것이다.
(각주- 왜 다른 input상에서 순차적으로 시행하는 것이 아니라, 자연수 사이에 알고리즘을 교차로 interleave하는 것일까? 이는 만일 알고리즘 Π이 어떤 인풋상에서 영원히 실행되는 경우를 고려해보면 알 수 있다)
여기에 이러한 발상을 시행하는 방법이 있다.
만일 W가 공집합이라면, 이는 자명하게 효과적으로 열거가능하다. 따라서 W는 공집합이 아니며, s가 W의 원소라 하자. 이제, pairing function( f : N -> N^2 s.t. 자연수와 유리수사이 bijection이 존재함을 증명할 때, 사용된 함수-section 2.4 참고)을 고려하자면, 각각의 수들의 가능한 쌍 (a, b)는 수 n과 함께 효과적으로 일대일 상관관계를 가진다(effectively one-to-one correlated). 그리고 이 경우 computable function이 존재하는데, pairing 함수의 n번째 pair의 각각 첫번째 순서쌍의 구성요소를 출력값으로 가지는 fst(n)=a, snd(n)=b 인 함수가 존재한다.
이것들을 이용하여, 새로운 알고리즘 Π'을 다음을 따르는 것으로 구성할 수 있다 :
주어진 입력값 n에 대해 a=fst(n), snd(n)=b를 계산한다. 이 다음 입력값 a 상에서 알고리즘 Π을 b단계 만큼 진행한다(우리는 알고리즘을 이산적으로 각 단계별 절차를 포함하는 것으로써, 그래서 그러한 단계를 셀 수 있는 것으로써 정의했었다). 만일 투입값 a상에서의 Π이 단계 b에 의해 어떤 출력값과 함께 중단된다면, Π'의 출력값을 a로 정의하고, 그렇지 않은 경우 Π'의 디폴트 값을 s로 두자.
n이 증가함으로써, 이 절차 Π'은 모든 인풋값 a에 대해, 단계 b의 모든 숫자에 대해 Π를 평가할 수 있다; 이는 단지 Π가 마침내 어떤 출력을 건내는 몇몇 인수 a들 만을 산출한다. 그래서 Π'는 Π'의 numerical domain W의 전체를 치역으로하는 함수를 계산한다. 그래서 W는 실제로 effectively enumerable이다. Q.E.D
b) 이제 이러한 발상을 고정하여, 가령 우리가 어떤 특정한 일반적 목적의 프로그램화된 언어 가령 C++과 같은 언어에서 작업한다고 해보자. 만일 수치적 함수 f를 계산하는 알고리즘이 존재한다면, 우리는 이러한 언어 안에서 시행할 수 있다. 말할 것도 없이, 이와 같이 수치적 알고리즘들의 모든 종류를 시행하는 것을 체계화하는 것에 적합한 범용 목적의 언어가 존재한다는 것은 비자명한 주장이다; 그러나 이러한 가정을 전적으로 합리적인 것처럼 보이게 만들어야 한다(still, even a passing familiarity with modern computing practice should make this assumption seem entirely reasonable)
(각주 - 좀 지나서 다시 논의를 튜링테제로 돌아올 때, 우리는 이러한 가정의 옹호를 더 알아볼 것이다)
그래서 마지막 정리(3.5)는 다음으로 따르게 된다 :
W가 수에 대한 e.e 집합이다 iff W는 우리의 가장 친숙한 범용 목적의 프로그래밍 언어에 지배된 어던 알고리즘의 수치적 정의역이다.
이제 우리의 프로그래밍 언어의 기오들의 모든 가능한 string들을 목록을 리스트화를 시작하자(어떤 '알파벳 순서'에서의 모든 길이 1 strings들, 그 다음 같은 순서 하에서의 길이 2의 string들, 길이 3에서의...) 그리고 그 언어 안에서의 구문론적으로 well-formed program 시행들의 열들이 되도록 하는 규칙을 지키고 복정하는 것을 단지 유지하자. 이것은 모든 가능한 알고리즘 Π_0, Π_1,Π_2,.. 들에 대한 효과적으로 발생된 목록들을 우리에게 준다. 이제 Π_e의 수치적 정의역을 W_e라 하자. 그렇다면, 우리의 마지막 정리(3.5)는 수를 원소로 가지는 모든 효율적으로 열가가능한 집합들이 W_e가 어떤 첨수 e에 의해 인덱스화 될 수 있다고 말한다. 이는 다음을 함의하는데
theorem3.6. 자연수를 원소로 가지는 모든 효과적으로 열거가능한 집합들의 집합 W는 그 자체로 열거가능하다.
pf) 이는 함수 f : |N -> W s.t. f(e) = W_e . 일 경우 f는 W를 열거할 수 있다(각주-f는 효과적인 열거인가?). Q.E.D.
정리 3.6.은 즉각적으로 다음 중요한 corollary를 연역한다.
theorem 3.7. 수에 대한 어떤 집합은 effectively enumerable하지 않고, 따라서 effectively decidable하지도 않다.
pf) 이미 자연수 집합 |N의 멱집합(power set) P(|N)은 열거될 수 없음을 안다. 그러나 우리는 정리 3.6에서 수를 원소로 가지는 효과적으로 열거가능한 집합들의 집합이 열거되어짐을 봤다. 따라서 W은 P(|N)이 아니다. 그러나 자명하게 W⊆P(|N)이다. 그래서 W에 없는 P(|N)의 원소가 존재해야 한다. 즉 수를 원소로 가지는 집합이 효과적으로 열거가능하지 않은 것이 존재한다. 정리 3.3은 이러한 집합을 수반하며, 말할 것도 없이 이들은 효과적으로 결정적이지 않은 것이다. Q.E.D.
3.5. The basic theorem about e.e. sets
단순하지만 중요한 정리인 theorem 3.5와 함께 우리는 effectively enumerable sets of numbers에 관한 basic theorem으로 불려도 손색이 없을 만한 정리를 증명할 것이다.
theorem 3.8. effectively enumerable set of numbers인 집합 K가 존재하지만 그것의 여집합 K*는 effectively enumerable하지 않은 것이 존재한다.
pf) 우리는 또 다른 diagonal construction을 사용할 것이다.
K= {e | e in W_e}라 하자. 이경우 다음이 따라 나오게 된다.
K의 여집합 K*는 effectively enumerable하지 않다 :
정의에 의해 임의의 e in K* iff e not in W_e. 따라서 K는 주어진 어떤 효과적으로 열거가능한 집합 W_e와도 동일하지 않다. 따라서 K는 효과적으로 열거가능한 집합 중 하나가 아니다(왜냐하면, W_e들이 그러한 것들의 전부이기 때문이다)
K는 effectively enumerable :
우리는 theorem 3.5를 증명했던 발상에서의 작은 변형을 이용할 것이다. K가 effectively enumerable하지 않기에, K는 |N의 전체 그 자체가 아니다. 그래서, K는 공집합이 아니다. 따라서 s in K. 이제 효과적인 절차 Π''이 다음을 따르는 것으로 고려하자 :
주어진 input n에 대해 a=fst(n), b=snd(n)을 계산하자. 그렇다면, 우리는 알고리즘 Π_a를 찾을 수 있고, 인풋 a상에서 b번의 단계 동안 이 알고리즘을 시행할 수 있다. 만일 인풋 a상에서 Π_a가 단계 b에 의해 어떤 산출값과 함께 알고리즘이 중단된다면, Π''는 b를 산출한다 하자. 그렇지 않을 경우 Π''는 기본 값 s를 산출한다고 하자.
n이 증가할 수록, 이 절차는 값 a, b의 값에 대한 모든 순서쌍에 대해 시행된다; 그래서 Π''의 산출값은 모든 수 a에 대한 집합인데, 그러한 수는 Π_a 의 numerical domain에 있다,
즉 이 집합은 a in W_a인 수 a의 집합, 즉 K이다. 그래서 K는 effectively enumerable하다. Q.E.D
즉각적인 corollary로써 우리는 theorem 3.7을 강화할 수 있는데, 이는 어떤 수의 집합이 결정적이지 않다고 말한다 :
theorem 3.9. 어떤 effectively enumerable sets of numbers are not decidable
pf) K를 e.e. set이지만, 그것의 여집합은 e.e.가 아니라 하자. 만일 K가 결정가능하다면, 그것의 여집합 역시 그러하다. 이는 정리 3.2에 의한다. 그럴 경위 K의 여집합 K*가 e.e.가 되는데, 이는 theorem 3.3에 의하므로 이는 모순이 된다. 따라서 K가 결정가능하지 않다. Q.E.D
recall)
theorem3.2. 만일 집합 Σ가 수에 관한 효율적으로 결정가능한(effectively decidable) 집합이라면, 그것의 여집합도 그러하다.
theorem3.3. 만일 집합 Σ가 수들의 효과적으로 결정가능한(effectvely decidable) 집합이라면, 이것은 효과적으로 열거가능하다.