https://blog.naver.com/wnstkd1928/223277085551
Peter Smith 교수가 저술한 괴델의 불완전성 정리에 대한 교과서(?) 입니다. 많은 논리학 교과서에 불완전성 정리가 어떻게 증명되는지에 대한 사전 예비 개념들과 함께 증명들을 소개한 책들이 많지만, 이만큼 천천히 자세히, 상세히 설명한 책은 보지 못했습니다(물론 제가 많은 책들을 알지 못하지만요).
요즘 불완전성 정리에 대한 공부 겸, 영어 공부 겸해서 블로그에 책 번역글을 올리고 있습니다.
영어 실력이 좋지 않아 정확한 직독직해나, 요약이 불가능해 글이 단어 뜻 그대로 옮겨적는 경향이 강합니다. 그래서 이런 비루한 영어실력의 번역을 올려도 되나 싶은 생각이 강한데, 문제가 심하다면 삭제하겠습니다.
이 책에 대해 만약 관심있으신 분들은 이 책은 구글에 Peter 교수가 무료로 배포한 것이 있으니 찾아보시길 바랍니다.
- Effective computability
우리는 이제 effectively computable function들에 대해 더 구체적으로 집중을 좁힐 것이다. 이후, 다시 여기서의 몇몇 발상들에 대해 더 좁고, 기술적으로 다루기 위해 돌아올 것인데, 이를 위해서 본 장에서는 일단, 비형식적이고 직관적인 묘사를 우선 다루는 것으로 충분하다.
우리는 우선 여기서 이와 관련된 중요한 개념인 effectively enumerable set을 소개할 것이다. 즉, 이는 effectively computable function에 의해 열거될 수(be enumerated)있는 집합이다.
3.1. effectively computable functions
a) 가령 수를 제곱하거나 두 수의 최대공약수를 찾는 루틴은 우리에게 주어진 input값으로 부터 몇몇 함수에서의 값에 대해 효과적으로 계산하는 것(effectively computing)에 대한 방법을 우리에게 준다 : 우리는 이것을 전적으로 기계적이라 말할 것이다.
우리는 논리학 교실에서 새로운 루틴을 배울수 있다. 가령, 두 적형식(well-formed formula, 이하 wff)를 가지는 꽤 자명한(trivial) 구문론적 계산이 존재하고, 또한 이 두 적형식은 그들의 연언을 생산하며, 그리고 유일하며, 약간의 덜 사소한 절차가 존재하는데, 이는 wff의 명제적 계산에 대한 진리값을 그것의 원자 명제들의 값에 대한 함수로써 효율적으로 계산하는 것을 위한 절차이다.
여기서 효과적으로 계산적인 절차(effectively computable procedures)를 말하는 것에 대한 의미는 무엇인가? 핵심은 효과적인 계산은 (1) 알고리즘을 수행하는 것인데, 이는 (2) 성공적으로 종료되는 것이다.
- 알고리즘은 순차적인 명령들의 집합이며(명령들은 그들의 수행에 앞서 고정되어야 한다), 각 단계는 모든 디테일 속에서 명백히 구체화 되어야 한다(여기서 모든 것이 상세하다는 것은 단계를 수행하는 것으로써 어떤 것이 다뤄지고 다뤄질 수 없는지에 대한 의심의 가능성이 없어야 하며, 가능성의 여지에 있어서도 없어야 한다).
알고리즘을 수행하는 것은 (1) 이산적인 step-by-small-step(여기서 각 small step은 매우 제한된 계산 에이전트나 기계에 의해 쉽게 수행되는 것을 일컫는다)의 절차들의 열(sequence)이 전체적으로 결정된 것을 포함한다. 또한 (2) 수행에 있어 상상력이나 직관 인간 판단의 오류의 실행에 대한 가능성이 없어야 한다. 또한 알고리즘을 수행하기 위해 (3) 우리는 외부의 oracles(즉, 정보의 원천과 독립된)에 의존하지 않아야 하며, (4) 우리는 랜덤한 방법을 가지면 안된다.
요약하자면, 알고리즘을 수행하는 것은 적합한 결정론적으로(deterministic) 계산하는 기계에 의해 행동하는 어떤 것으로 우리는 말할 수 있다.
- 그러나 더 분명하게 : 만일 알고리즘을 수행하는 것이 실제로 전체 함수를 계산하는 것이라면, 그 절차는 모든 인풋에 대해 유한한 단계 안에서 절차가 종료되어야만 하고, 올바른 종류의 아웃풋을 생산해야 한다. 참고로, 그것의 수행이 항상 종료되는 것은 알고리즘의 아이디어 바로 그 아이디어의 부분에 속하는 것이 아니다; 그래서 일반적으로 알고리즘은 부분함수만 계산할 수 있다.
이러한 두 생각과 함께 우리는 최신 개념을 얻을 수 있다.
1항 전체(total) 함수 f : Δ -> Γ 가 효율적으로 계산가능하다(effectively computable)은 iff 어떠한 알고리즘이 존재한다는 것인데, 이는 유한한 단계 속에서 임의의 주어진 domain Δ로 부터의 input 값에 대해 계산하는 것에 사용되는 것이다.
다항함수와 관련된 일반화된 정리도 이와 유사하다.
(b) 비형식적으로 말하자면, 효율적으로 계산가능한 함수는 컴퓨터가 계산할 수 있다는 발상이다! 그러나 우리가 여기서 생각하는 컴퓨터의 종류는 무엇인가? 우리는 컴퓨터의 크기, 속도, 그리고 이것의 설계(architecture)와 관련된 것에 대해 더 말하는 것이 필요하다.
실제 컴퓨터는 크기와 속도가 제한되어 있다. 즉, 그것이 다룰 수 있는 인풋의 크기의 상계가 존재할 것이며, 그것이 저장할 수 있는 명령들의 집합의 크기에 대한 상계가 존재할 것이다; 그리고 이것이 작동하는 메모리의 크기에 대한 상계도 있을 것이다. 심지어 우리가 인풋과 명령을 우리의 컴퓨터가 다루게 입력을 해도, 만일 그것이 수 세기 동안 그것의 알고리즘적 절차를 수행하는 것이 끝나지 않는다면, 그것의 소용은 거의 없을 것이다.
그러나 우리는 기꺼이 추상화 할 수 있는데, 즉, 우리는 시간과 기억공간이 충분히 주어졌단 하에서 임의의 특정한 인수들에 대해 함수의 값을 계산하는 것에 이용되는 원칙 안에서 컴퓨터가 사용하는 순차적인 명령들의 유한 집합이 만일 존재할 경우, 우리는 함수를 절차적으로 계산가능한 것으로써 다룰 수 있다.
다시 명백하게 표현하자면 : 여기서 effective는 계산이 실제 시간 동안 존재하는 컴퓨터들 상에서 우리에게 실현 가능해야 함을 의미하지 않는다. 이것은 알고리즘이 이론안에서 작업을 하고, 끝으로 결과를 건내는 알고리즘이 존재한다는 것으로도 충분하다, 이는 오직 우리가 그것을 이용하기 위한 계산적 리소스들을 가지고 있고, 충분히 길게 기다릴 수 있다는 전제하에서 가능하다.
그러나 우리는 이렇게 물을 수 있을 것이다 "만을 우리가 우주의 생에 동안 아웃풋을 건내지 않을 절차들을 하거한다면, 그게 무슨 소용인가?" 만일 우리가 계산가능성의 문제에 흥미를 가진다면, 우리는 원리적으로 이상화 된 계산가능성(idealized-computability-in-principle)에 관해 관심을 가지지 않고, 실행가능한(practicable) 계산가능성에 관심을 가져야 하는가?
이는 합리적인 요구이다. 그리고 현대 컴퓨터 과학은 심지어 계산적 복잡성의 등급과 실현 가능성의 레벨들에 대해 할 말이 많다. 그러나 우리는 계산가능성의 궁극적 이상화 된 개념(ultra-idealized notion of computability)을 고수할 것이다. 왜냐하면 이후 우리는 제한적 정리들에 관한 범위를 증명할 것이기 때문이다. 가령 왜 알고리즘적으로 계산될 수 없는가에 관한 것. 계산가능한 것이 되기 위해 요구되는 것이 무엇인가에 대한 매우 약한 '원리적인(in principle) 개념과 함께 작업함으로써, 우리의 불가능성의 결과들은 그에 따라 매우 강력해질 것인데, 우선 시작은 우리의 주어진 제한과 시간의 제약 혹은 리소스들을 고려할 때, 그것은 실행가능한 것에 대한 단지 우연한 것에 의존하지 않을 것이다. 그들은 몇몇 수치(numerical) 함수들은 알고리즘적으로 계산될 수 없음을 보여준다. 심지어 그 발상에 대해 가장 관대한 이해 상에서도 말이다.
c) 우리는 저장고 상에서의 제약 등으로부터 추상화 할 수 있다. 그러나 우리는 여전히 의심이 가능한데, 계산 장치의 건설이 그것이 계산할 수 있는 것에 영향을 끼치진 않는가에 대해서이다. 짧게 말하자면 그렇지 않다(적어도 '일반적인 목적'으로써의 컴퓨터로써 행위하는 컴퓨터의 복잡성에 관한 특정한 정도의 장치를 우리가 다루는 한에서).
....(중요하지 않은 불필요한 설명들이라 생략했습니다)
게다가 진지하게 제안되어진 다른 설계(archtecture)와 함께하는 이상화된 컴퓨터에 의한 알고리즘적 계산가능성의 모든 상세한 정의들은 동등한 것으로 드러나는데, 이는 알고리즘적 계산가능성은 설계와 독립적이라는슬로건으로 나타낼 수 있다.
d) 마지막 주요 주장에 대한 고려는 중단하고, 조금 천천히 두가지 단계를 고려할 것이다.
first stage: 수치 함수(가령, 공역과 정의역이 자연수인)를 효율적으로 계산하는 것에 대한 발상을 정제하는 다양한 제안된 방안들의 상호 동등에 관한 절차적(technical) 결과가 존재한다 - 우리는 마침내, 매번 튜링-계산가능한 수치함수들의 같은 부류(class)와 함께하게 된다. 이것은 형식적 메타 수학적 정리이다(혹은 정리의 단서(우리가 각 상황 별 증명할 수 있는)가 된다) 그러나 이것은 튜링의 가장 유명한 테재를 지지한다 :
Turing's Thesis : 수치함수, 이는 비형식적 의미에서 효율적으로 계산가능한 함수인데, 이는 비형식적인 의미로 단지 실제로 적합한 튜링 기계에 의해 계산가능한 함수이다.
그러나 튜링 기계는 작업하기에 열악하며, 우리는 대신 현대의 일반적 목적의 컴퓨터상에서 계산가능한 수치적 함수를 대신 생각하길 원하며, 우리가 가장 선호하길 원하는 컴퓨터 언어를 사용킬 원한다. 그렇다면, 튜링의 thesis는 이와 입증적으로 동치가 된다 : 효율적으로 계산가능한 수치함수들은, 비형식적 의미로, C++로 적힌 알고리즘들을 사용하는 원리에 대한 계산가능한 그러한 함수가 된다.
튜링의 thesis(각주 - Turing's Thesis has a twin you might have heard of, namely Church's Thesis: we'll explore that as well, and the interrelation between the two, in Chapters 38 and 44)는 날카로운 기술적 해석과 함께 비형식적 개념과 연관된다. 그래서 너는 아마 이것은 우리가 증명했다고 말하는 종류의 것이 아니라 생각할 수 있다. 그러나 확실히 75년이 지난 후에도 튜링의 테제에 성공적으로 도전한 것에 이른 것은 없다. 이는 효율적으로 계산가능한 수치적 함수에 관해 비형식적으로 말하는 것을 지속하는 하는 것을 의미하며, 그리고 그러나, 우리가 완전히 확정적인 부류를 언급하고 있다는 것에 매우 확신하는 것을 의미한다.
e) second stage : 효과적으로 계산하는 함수를 비-수치적 함수들로 확장하는 것에 대한 것은 어떨까? 이 생각은 결정적인가(determinate)?
여기에 자연스러운 제안이 있다 : 임의의 계산, 이는 충분히 이산적이고 구분되는 유한 대상들-X들-을 다루는,이 다른 X들에 대한 단순한 수치적 코드를 사용하는 트릭을 경유하여 동등한 수치적 계산으로 드러날 수 있다. 즉, 각각 상대적으로 자명한 알고리즘에 의해, 우리는 X들을 수로 지정할 수 있다; 그다음 우리는 숫자 상에서 적절한 코어 계산을 행할 수 있으며, 그 다음 다른 사소한 알고리즘을 X들에 대한 주장으로 결과를 되돌아가는 번역을 한다. 그래서 만일 어떠한 수치적 함수가 효율적으로 계산가능한지 결정된다면, 적합한 유한대상들에 대한 다른 함수들에도 동일하게 적용된다.
다행히도, 그러나, 우리는 그것의 가장 완전한 일반화에 대한 논의로 접근하기 위해 중단할 필요가 없다. 이 책의 목적에 대해, 우리가 가장 흥미로워하는 비-수치적 계산들은 X들이 표준적 형식 언어들로부터의 표현들(expressions) 혹은 표현들의 열(sequences of expressions)등인 경우에 해당된다. 그리고 이러한 경우들 속에서, 우리는 알고리즘적으로 그러한 것들에 관한 주장을 수들과 관련된 상응하는 주장들로 지정할 수 있다. 그래서 우리는 주어진 튜링의 테제를 고려할 때, 표현들 등에 대한 효율적으로 계산적인 연산자로써 무엇을 다룰 수 있는가에 대한 것 역시 결정적이라 가정할 수 있다.
3.2. Effectively decidable properties and sets
a) 우리는 자주 우리는 알고리즘적 루틴들을 함수들을 계산하는데 사용할 뿐 아니라 하나의 속성이 고정 되는지의 여부를 결정하는데도 이용한다. 가령 주어진 수에 대해 9에 의해 나눠지는지의 여부를 알고리즘적으로 테스트하는 루틴이 존재할 수도 있고, 논리학에선, 주어진 기호들의 줄(strings)이 wff인지의 여부에 대해 결정하는 것 등에 대해 배운다.
이러한 사례와 관련하여, 몇 가지 정의를 알아보자 :
하나의 속성(property)나 관계(relation)이 효과적으로 결정가능하다(effectively decidable)는 것은 적합하게 프로그램화 된 컴퓨터가 유한한 수의 단계 안에서 그 속성이나 관계가 어떠한 주어진 항목들(items)에 적용할 수 있는지에 대한 여부를 결정할 수 있는 알고리즘적 절차가 존재한다는 것과 동치이다.
여기서 '효과적임'은 'practicable'이나 'efficient'를 의미하진 않는다. 속성이 효과적으로 결정가능하다는 것은 주어진 대상이 그것을 가지는지의 여부를 해결하는 계산적 리소스와 시간의 량이 많을지라도 가능한 것이다. 이것이 요구되어지는 모든 것은 주어진 원리안에서 그 작업을 할 수 있는 어떠한 알고리즘이 존재한다는 것이다.
b) 이 다음으로, 우리는 수들 사이에 유지되는 결정가능한 관계들과 그리고 수에 관한 결정가능한 속성들에 주위를 돌릴 것이다. characteristic function의 정의를 생각하며, 다음의 대안적 정의를 소개한다 :
수치적(numerical) 속성이나 혹은 관계가 효과적으로 결정가능하다는 것은 iff 그것의 characteristic function이 효과적으로 계산가능하다는 것이다.
실제로 우리의 두 정의가 수치적 속성들에 관한 이러한 경우에 대해 부합한다는 것을 확인하자. n이 P인지의 여부에 대해 결정하는 알고리즘이 존재한다 가정하고, 이러한 알고리즘은 yes/no에 대한 의견을 건내는데 : 이는 '만일 대답이 yes일 경우 0인 output값을 산출하고 그렇지 않을 경우 1을 내놓는' 시행을 더하는 것으로 간주할 수 있고 이렇게 된다면 우리를 cp(n)을 계샇나는 것을 위한 알고리즘을 가질 수 있다.
역으로 cp(n)를 계산할 수 있는 알고리즘을 가진다면, 우리는 n이 P인지의 여부에 대해 결정하기 위해 '만일 값이 0이라면, output을 yes로 두고 그렇지 않으면 no'인 조건을 추가할 수 있다.
튜링의 테제에 의해, 효과적으로 계산가능한 수치적 함수의 개념이 확정적(determinate)이기 때문에, 마찬가지로 효율적으로 결정가능한 수치적 속성 혹은 관계의 개념도 그러하다.
그렇다면, 비-수치적인(non-numerical) 효과적으로 결정가능한 속성에 관한 아이디어는 무엇이 될 수 있는가? 우리는 이 개념을 확정할 수 있는가? 우리는 단순한 알고리즘적 방법으로 수를 사용하는 표현들의 열 혹은 열들과 같은 유한 대상들을 표현할 수 있다. 그래서 가령, formula의 특정한 속성이 결정가능한 것이라는 것은 논쟁의 여지 없이 다음의 질문으로 번역되어질 수 있다 : "수들의 상응하는 속성이 결정가능한가?"
숫자들의 결정가능한 속성으로써 간주되는 것은 꽤 명확하기(determinate)때문에, 형식적 표현들 혹은 표현의 열들의 결정가능한 속성들로써 간주되는 것이 꽤 명확하다는 것이 따라 나온다.
c) 속성들에 관한 논의를 그들의 확장(extension)으로 논의를 옮겨서 얘기할 것이다.
(각주 - 속성의 extension은 그 속성을 가지는 대상들의 집합이다. 마찬가지로 관계의 확장은 그 관계를 지지하는 대상들의 순서쌍들의 집합이다)
임의의 집합 Σ가 효율적으로 결정가능하다는 것은 iff 알고리즘적 절차가 존재한다는 것인데, 이는 적합하게 프로그램화된 컴퓨터가 유한한 단계 속에서 임의의 관련된 주어진 대상이 Σ의 원소인지의 여부에 대해 결정할 수 있는 것에 사용할 수 있는 절차이다.
Σ가 수들의 집합인 특별한 경우일 상황에는, 우리는 이러한 정의를 좀 더 예리하게, 위와 평행하는 정의인 것으로 수정할 수 있다.
자연수들의 집합 Σ⊆|N이 효과적으로 결정가능하다는 것은 iff 속하는 속성에 관한 characteristic function이 효과적으로 계산가능하다는 것이다(즉, 이 함수 cΣ은 만일 cΣ(n)Σ에=0 if n in Σ, 그렇지 않으면 cΣ은 1을 산출)
튜링 테제를 감안할 때, 수들의 효과적으로 결정가능한 집합에 관한 이러한 아이디어는 또 다른 날카롭게 명확한 것으로 만들게 된다. 다시, 적어도, 우리가 수에 의해 잘 표현될 수 있는 유한한 대상들을 다룰 때, 그러한 대상들의 효과적으로 결정가능한 집합에 대한 이 생각은 동등하게 결정적인(determinate) 것으로 간주할 수 있다
d) 다음 두 가지 정리를 확인해보자
theorem3.1. 자연수에 관한 임의의 유한 집합은 효과적으로 결정가능하다.
pf) Σ⊆|N이 유한하다면, characteristic function cΣ은 유한한 인수들을 제외하면, 항상 1의 값을 산출할 것이다.그러한 함수는 가령, 예외적인 인수들에 대한 유한한 목록을 확인하는 식으로 가령 인풋 값이 목록의 예외적 인수들과 일치하면, 0을 출력하고, 그렇지 않은 경우 디폴트 값으로 1을 산출하는 무차별 대입(brute-force)알고리즘에 의해 효율적으로 계산가능하다.
theorem3.2. 만일 Σ가 수에 관한 효과적으로 결정가능한 집합이라면, 그것의 여집합도 그러하다.
pf) 만일 cΣ이 효과적으로 계산가능하다면, 함수 cΣ는 쉽게 정의될 수 있는데,
가령 cΣ(n) = 1 - cΣ(n)으로 정의될 수 있다. 그러나 cΣ*는 명백히 Σ의 여집합에 대한 characteristic function이 된다.
유한한 집합의 여집합은 무한하기 때문에, 이러한 정리는 수들의 결정가능한 무한집합이 존재한다는 것이 따라 나온다. 또한 그것의 여집합이 무한집합이면서 결정가능한 집합인 무한 집합 또한 존재할 수 있다. 가령 소수들의 집합이 그럴 수 있지만, 수들의 비결정적인 집합 역시 존재함을 이후 볼 것이다.