2024-04-03-01. 이발사 문제, 정지 문제
이발사 문제
어떤 섬에는 이발사가 한 명 있는데, 이 이발사는 자기 스스로 이발을 하지 않는 사람만 모두 이발을 해 준다.
이발사의 머리는 누가 이발을 해 주는가?
- 스스로 이발을 한다면 → 이발사가 이발 해 주면 안됨
- 스스로 이발을 하지 않는다면 → 이발사가 이발을 해 주어야 함
따라서 이발사가 자기 스스로 이발을 하지 않는 사람만 모두 이발을 해줄수는 없다.
위 이발사 문제에 의해 아래와 같은 심각한 결과가 도출된다.
- 러셀의 역설 : 집합론이 재정의되는 결과를 가져옴
- 괴델의 불완정성 정리 : 자동 증명 분야의 중요한 정리
- 어쩌면 P-NP 문제와도 상관이 있다.
정지 문제 (HALTING Problem)
컴파일러가 프로그램이 멈추지 않는 것을 알려주면 편할 것이다.
문제 : 프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행시키면 M은 언젠가 종료될 것인가?
M(X) : 프로그램 M에 입력X를 주고 실행시킨 상태
다음과 같은 문장이 성립할 수 있다.
- M(X)는 종료한다 or 종료하지 않는다
- M(X)의 출력은 Yes이다/No이다
- M(X)의 출력은 01001010이다
- ...
문제를 다시 말하면, 어떤 프로그램이 종료하지 않는지를 돌려보기 전에 알 수 있는가?
- 돌려봐서 끝나면 끝난다는 것을 알 수 있지만, 안 끝나고 있으면 언젠가 끝난다거나 절대로 안 끝난다는 것을 알 수 없다.
Alan Turing의 증명
HALTING Problem은 풀 수 없다. 귀류법을 통해 증명.
- 프로그램 D가 존재해서, 모든 프로그램 M과 M에 대한 모든 입력 X에 대해 M(X)가 종료될지를 판단할 수 있다고 가정한다.
- 프로그램 D는 Yes/No만을 대답함.
- 프로그램 D는 항상 종료됨.
- 이를 "프로그램 D가 정지 문제를 결정(Decide)한다" 라고 한다.
- 즉, 프로그램 D의 입력은 어떤 프로그램과 그 프로그램에 주어질 입력이고, 출력은 종료 여부이다.
- 프로그램 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의 입력으로 줄 수 있음.
- S(S)가 멈추는 경우 S(S)는 멈추지 않고, S(S)가 멈추지 않는 경우 S(S)는 멈춘다.
Hacking을 막아 보자
배경 : 어떤 연구소 과제
목표 : 웹 서비스 PHP코드 해킹 방지
방법 : PHP 소스 코드를 분석해서 해킹 공격에 취약한 부분이 있는지 보자.
예) 사용자 입력에 DB query 구문이 있는지 확인
취약한 부분을 모두 찾아내는 알고리즘이 존재할까?
모든 경우를 다 확인할 수는 없다. 그냥 봐도 경우의 수가 너무 많다.
과제 담당자 : 잘 따지면 모든 경우를 다 찾을 수 있는데 제대로 못하고 있다
-> 그렇지 않다. 불가능하다는 증명이 있다 -> 이 문제가 풀리면 HALTING이 풀림
PHP 코드를 멈추지 않는 형태로 바꾼다. 원래 코드가 해킹된다면 바꾼 코드도 해킹되고, 반대도 성립하도록 한다.
어떤 해킹 방법이든 사용할 수 있는 해커를 가정하고, 해커는 해킹에 성공할 경우 PHP코드가 멈추도록 한다고 문제를 정의한다.
이는 정지 문제와 다르지 않다.