01. halting problem [1 2주차]

1. HALTING Problem [1-2주차]

2024년 1월 9일 화요일

오후 10:41

<HALTING Problem>

문제 : 프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행시키면 M은 언젠가 종료될 것인가?

(그렇지 않으면 무한 루프를 돌 것인가?)

 

구체적인 하나의 경우가 아니라 모든 경우에 대한 답을 할 수 있어야 한다.

 

M(X) : 프로그램 M에 입력X를 주고 실행시킨 상태

 

다음과 같은 문장이 성립할 수 있다.

• M(X)는 종료한다/ 종료하지 않는다
• M(X)의 출력은 Yes이다/No이다
• M(X)의 출력은 01001010이다

 

위 문제의 유용성 : 컴파일러가 프로그램이 멈추지 않는 것을 알려줄 수 있다면 좋을 것이다.

 

그냥 돌려보면 안되나?

-> 돌려봐서 끝나면 끝난다는 것을 알 수 있지만, 안 끝나고 있으면 언젠가 끝난다거나 절대로 안 끝난다는 것을 알 수 없다.

 

for( ; ; ){ }는 안 끝난다는 것을 알 수 있다. “잘 따지면” 되지 않을까?

 

 

<Alan Turing의 증명>

HALTING Problem은 풀 수 없다. 귀류법을 통해 증명.

 

1. 프로그램 D가 존재해서, 모든 프로그램 M과 M에 대한 모든 입력 X에 대해 M(X)가 종료될지를 판단할 수 있다고 가정한다.

    - 프로그램 D는 Yes/No만을 대답함.

    - 프로그램 D는 항상 종료됨.

이를 "프로그램 D가 정지 문제를 결정(Decide)한다" 라고 한다.

즉, 프로그램 D의 입력은 어떤 프로그램과 그 프로그램에 주어질 입력이고, 출력은 종료 여부이다.

    - D(M, X) -> Yes/No -> 종료

 

2. 프로그램 D가 있다면, D를 이용하여 다음 D’과 S를 쉽게 만들 수 있다.

• D’(M, X) : M(X)가 멈추는 경우 D’(M, X)는 멈추지 않고

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

  - D(M, X)의 출력이 No이면 멈추고, Yes이면 무한루프

• S(M) : M(M)이 멈추는 경우 S(M)은 멈추지 않고,

   M(M)이 멈추지 않는 경우 S(M)은 멈춘다.

    - D’(M, M)을 돌리기만 하면 됨.

    - M은 프로그램이지만 문자열일 뿐이므로, D’과 M의 입력으로 줄 수 있음.

 

3. S(S)를 돌리면?

S(S)가 멈추는 경우 S(S)는 멈추지 않고

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

->모순

따라서 D는 존재하지 않는다.

 

 

<Hacking을 막아 보자>

배경 : 어떤 연구소 과제

목표 : 웹 서비스 PHP코드 해킹 방지

방법 : PHP 소스 코드를 분석해서 해킹 공격에 취약한 부분이 있는지 보자.

예) 사용자 입력에 DB query 구문이 있는지 확인

 

검사 방법이 모든 경우를 다 확인할 수는 없음. 그냥 봐도 경우의 수가 너무 많다.

과제 담당자 : 잘 따지면 모든 경우를 다 찾을 수 있는데 제대로 못하고 있다

-> 그렇지 않다. 불가능하다는 증명이 있다 -> 이 문제가 풀리면 HALTING이 풀림