var i_able

수학적 귀납법은 재귀 함수를 구현할 때 흔히 이용된다. 더 간결하고 효율적인 코드를 짤 때 재귀 함수를 이용하는 경우가 있다. 내가 짠 재귀 함수가 정확한지 판단하기 위해 수학적 귀납법에 대해 알아보자.

수학적 귀납법

기본형: P(1)이 참이고, P(n-1) -> P(n)이 참이면 모든 자연수 n에 대하여 P(n)이 참이다.

• Base: P(1)
• Step: P(n-1) -> P(n)

강한 형태: P(1)이 참이고, P(1)∧P(2)∧...∧P(n-1) -> P(n)이 참이면 모든 자연수 n에 대하여 P(n)이 참이다.

• Base: P(1)
• Step: P(1)∧P(2)∧...∧P(n-1) -> P(n)

Step: P(n-1) -> P(n)

P(n-1)이 참이라면, P(n)이 참이다

귀납법에서 Base가 참임을 증명한 후 Step을 증명할 때, P(n-1)을 이용해 P(n)을 만들어낸다. 만약 P(n-1)에서 도출된 식이 P(n)과 일치한다면 모든 자연수 n에 대해 P(n)이 참이다. P(1)이 참이므로 P(2)가 참, P(2)가 참이므로 P(3)이 참, ..., P(k-1)이 참이므로 P(k)가 참, 으로 이어진다.

여기서 의문이 들 수 있다. P(n-1)이 참이란 가정에 문제가 없나? P(n-1)이 거짓일 땐 고려하지 않아도 되나? 사실 난 이런 의문이 들지 않았다. P(n-1)이 참이란 건 '가정'이고, P(1), 즉 Base에서 시작될 명제가 아닌가? 거짓이 되면 그냥 P(1)에서 끝나는 것 아닌가? 애초에 P(n-1)이 거짓이 된다면 명제가 거짓이 되는 자연수가 존재한다는 뜻 아닌가?

Vacuously True

그런데 코드상에서 보면 헷갈리는 경우가 있다. 재귀 함수를 구현할 때, 내가 return한 값이 입력에 대해 정확한 출력을 제공한다고 확신할 수 있을까? 이럴 때 return문 내에서 호출하는, 이전 수에 대한 호출의 값이 정확하다고 '믿어'야 한다. 그 부분이 바로 P(n-1)이고, P(n-1)이 거짓일까 걱정하지 않아도 된다. P(n-1)이 맞다는 가정 하에 추가한 연산의 결과가 P(n)이 된다면 말이다! Base인 경우와 return문, 즉 Step만 생각하면 되는 것이다.

int sum(int x) {
    if (x <= 0) return 0;	// Base
    return x + sum(x-1);	// Step
}

이는 P(n-1)이 거짓인 경우는 'Vacuously True' 이기 때문이다. Vacuous는 텅 빈, 공허한 이라는 뜻을 갖는다. Vacuously True, '텅 빈 진실'은 전제가 거짓일 때 전체 명제에 해당한다. 전제가 거짓인 경우엔 결론이 참이든 거짓이든 명제는 참이 되는 것이다. p->q, 즉 'p이면 q이다'에서 p가 아닐 땐 q가 무엇인지 정의하지 않았기 때문에, p가 거짓이면 q가 무엇이든 참으로 보는 것이다. p->q가 거짓이 되려면 반례, p가 참일 때 q가 아닌 경우가 있어야 하는데 p가 거짓이 되면 반례를 따질 수 없다.

최소 반례 논법

그렇다면 P(n-1)이 거짓일 때는 step이 vacuously true가 된다는 것을 알았다. 그런데 P(n-1)이 거짓이라면, 결국 P(n)이 거짓이 되는 자연수 n이 존재한다는 거 아닌가? 여전히 뭔가 찝찝하다. Vacuously true가 실제 결론과 충돌하지 않는 이유를 살펴보자.

m > n₀에 대해, 가장 처음으로 P(n)이 거짓이 되는 n을 m이라고 하자. 

1. 반례 집합 S = {  n∈N | ¬ P(n) }가 비어 있지 않다고 가정.
2. 그중 가장 작은 원소 m = min⁡S를 잡음.
3. m ≠ n₀ → m−1 < m → P(m−1) 은 참.
4. step에 의해 P(m)도 참이어야 함 → m ∈ S 와 모순.
5. 모순이므로 S는 공집합 → 반례가 존재하지 않는다 → ∀n, P(n)

=> '만약 P(n-1)이 거짓인 n이 정말 있다면?'을 정면으로 부정

결국 Base가 참인 상태에서 Step 자체만 증명이 되면 Step의 전제, P(n-1)이 거짓이 되는 경우는 발생하지 않음을 알 수 있다. 그리고 Step 자체를 증명할 때 전제가 거짓이면 명제는 참이되므로, Step을 증명할 때 P(n-1)이 거짓이 되는 경우를 고려하지 않는다.

sum()에서 x == 0일 때 sum(x)가 참이고, sum(x-1)이 참일 때 x + sum(x-1)이 sum(x)의 값을 반환한다면 sum(x-1)이 거짓이 되는 경우가 발생하지 않는다.

결론

뭔가 헷갈리고 다 어렵다. 사실 간단한 수학식에 적용하면 당연하지 않나? Vacuously True인 상황을 왜 고려하지? 라는 생각이 드는데 코드상으로 보면 또 P(n-1)이 미심쩍고 찝찝하긴 하다. 그런데 'Base'가 참이고, P(n-1)이 참이라고 가정하면 P(n)이 참이 되긴 한다! 하면 P(n-1)이 거짓이 되는 경우는 발생하지 않다고 보면 될 것 같다. 결국 P(n-1)도 P(n-2)가 참일 때 참이 되는 Step에 포함됐기 때문일 것이다.

문제

어떤 프로그램 M과 그에 대한 어떤 입력 X가 있을 때, M(X)는 종료를 하는가?

• M: 소스코드로 이루어진 프로그램
• X: 문자열
• M(X): 입력 X에 대한 M의 실행

M(X)를 실행하기 전에 종료 여부를 알고 싶음

• M(X)를 실행하면, 종료하지 않는 경우에 대해선 종료 여부 판단이 불가하기 때문
• 실행 전에 종료 여부를 알 수 있는 방법이 있는가?에 대한 문제
• for(;;)같은 코드는 종료 여부를 바로 알 수 있으니, 모든 경우에 대해서 판단을 할 수 있지 않을까?
• 판단이 가능한지 증명해보자

증명

• by Alan Turing
• 귀류법 사용

가정

M(X)의 종료 여부를 반환하는 프로그램 D가 존재

D

• D(M, X)의 반환값: Yes / No
• M(X) 종료 -> Yes
• M(X) 무한히 실행 -> No
• D는 반드시 종료

D'

D에 의해 D' 도출

• D'(M,X)는 M(X)가 종료되면 무한히 실행, M(X)가 무한히 실행되면 종료
• D'(M,X)는 D(M,X)가 Yes면 무한히 실행, D(M,X)가 No면 종료
• 소스코드상에서: D(M,X)의 결과에 따라 무한루프 or 반환
• D가 존재한다면, D'도 존재함

function D_(M, X) {	// D_ == D'
    if (D(M,X) == "Yes") {
        while(1) {};
    }
    return;
}

S

D'에 의해 S 도출

• S(M)은 M(M)이 종료되면 무한히 실행, M(M)이 무한히 실행되면 종료
• S(M)은 D'(M,M)이 종료되면 종료, D'(M,M)이 무한히 실행되면 무한히 실행
• 소스코드상에서 D'(M,M) 호출 -> 내부에서 D 호출 중
• D'이 존재한다면, S가 존재함

function S(M) {
    D_(M,M)
}

도출

M = S;

• S(S)는 S(S)가 종료되면 무한히 실행, 무한히 실행되면 종료
• M이 S일 때, S는 존재할 수 없게 됨
• 모순 발생!
• => D가 존재한다는 가정이 틀림

M(X)의 종료 여부를 판단하는 프로그램 D는 존재하지 않는다.

결론

Halting 문제는 풀 수 없다!

P와 NP가 다른 집합인가?

결정 문제: 답이 참 또는 거짓으로 결정되는 문제. P 문제와 NP 문제 모두 결정 문제

P(Polynomial-time) 문제: 다항 시간 내에 해결할 수 있는(= 쉽게 풀리는) 결정 문제들의 집합

NP(Non-deterministic Polynomial-time) 문제: 다항 시간 내에 검증할 수 있는 비결정적 결정 문제들의 집합

• 주어진 '힌트'에 의해 문제가 참임을 '검증'하는 것이 다항 시간 내에 이루어짐
• 해를 검증하는 것이 아닌, '모든 해를 구하는 것'은 다항 시간 내에 해결할 수 있는지 모름
  => P는 NP의 부분집합은 참,but P=NP인가?
  문제 검증이 다항 시간 내에 이루어진다면, 해를 구하는 것 역시 다항 시간 내에 이루어질 수 있는가?
  => 아직 증명되지 않음: P-NP problem

결정론적 알고리즘: 같은 입력이면 같은 출력 생성

• 수행 시간
  • '입력 크기'에 대한 다항식으로 표현: 일반적으로 입력 크기가 커지면 증가함
  • 최악의 경우 고려하여 분석

비결정론적 알고리즘: 같은 입력에 대해 같은 출력 생성하지 않을 수 있음

• 수행 시간
  • 보통 결정론적 알고리즘과 같은 방식으로 분석하지만, 무작위성을 가지므로 평균 수행 시간으로 분석하는 것이 일반적
  • 최선/최악의 경우 고려