[Lecture] The Halting Problem, 수학적 귀납법

Halting Problem

Q : 프로그램 M과 입력 X가 있을때, M에 입력 X를 주고 수행시키면 종료할 것인가?

A : 특수한 경우는 알 수 있으나, 모두 알 수 있다고 확신할 수 없다

돌려봤을 때, 언제 끝날지 모르기 때문에 '무한루프'가 절대로 안끝난다는 것을 확신할 수 없기 때문이다

 

어떤 프로그램이 종료하는지 알 수 있는 방법이 있을까?

 

D(M,X)은 프로그램 M에 X를 입력했을 때 멈추면(exit) Yes, 멈추지 않으면(loop) No 중 하나를 출력하고 항상 멈추는 프로그램이라고 가정하자

 

이해하기 쉽도록 exit - yes, loop - no를 사용한다

 

D라는 프로그램이 있으면, D' ,S 프로그램을 만들 수 있다

D'은 입력값에 의해 종료하면 프로그램을 실행하고, 종료하지 않을 경우 프로그램을 종료한다

M(x) 멈추는 경우 → D’(M,X) 멈추지 않는다

: yes → loop (no)

M(x) 멈추지 않는 경우 → D’(M,X) 멈춘다

: no → exit (yes)

 

D' 프로그램이 위와 같다면,

 

M(M) 멈추는 경우 → S(M) 멈추지 않는다

: yes → loop (no)

M(M) 멈추지 않는 경우 → S(M) 멈춘다

: no → exit (yes)

 

S(S) 멈추는 경우 → S(S) 멈추지 않는다

S(S) 멈추지 않는 경우 → S(S) 멈춘다

: 모순이다

 

위 문제 풀이에서 잘못된 부분은 "프로그램 D가 있다고 가정한 것"이다

 

이해를 더한 영상은 아래와 같다

https://youtu.be/92WHN-pAFCs?si=Q_L38HbaIyfE4-DA

 

---

수학적 귀납법

P(n)(문장)은 모든 자연수 n에 대해서 참이라는 것을 보이기 위해서 사용되는 기법이다

수학적 귀납법의 기본형 : P(1)이 참(Base)이고, P(n-1) → P(n)이 참(Step)이면 P(n)은 모든 자연수 n에 대해서 참이다

 

P(n-1)을 참으로 가정한다 = 참이 아니라 거짓이면 ?

 

P	Q	P → Q
true	true	true
true	false	false
false	true	vacuous true
false	false	vacuous true

 

vacuous ture를 편의상, true로 본다

false는 절대 아니기 때문에, 애매하지만 ture로 보는 것이다

 

ex) vacuous true 예시

if n > 3 → n^2  > 10 이 항상 사실인가?

n = 1 이라면 ? 

 

위 표에서 알 수 있듯이 P(n-1)의 true false 상관없이 P(n)의 진리값에 따라 P(n-1) → P(n)이 결정되는 것을 볼 수 있다

 

강한 수학적 귀납법

1. P(1)이 참이다

2. 임의의 자연수 K에 대해 P(1),P(2), .... P(k)가 참이면 P(k+1)도 참이다

(일반적인 수학적 귀납법은 임의의 자연수 k에 대해 P(k)가 참이면 P(k+1)도 참이 됨을 설명한다)

 

https://pkjung.tistory.com/140

수학적 귀납법 = 강한 수학적 귀납법