어제 올린 로또 번호 생성 프로그램을 보다, 문득 소개하고 싶은 것이 생겨 글을 씁니다.

예를 들어 말입니다, 제가 올린 로또 번호 생성 프로그램이 실제로 몇 번만에 로또 번호를 맞출 수 있는지 한번 검증해보고 싶어졌다고 해 봅시다. 그래서 저는 다음과 같은 프로그램을 작성하였습니다.

import random
 
def plusAll(a):
    result = 0
    for i in a:
        result += i
    return result
 
def lottoNumGen():
    while True:
        a = random.sample(range(1, 45+1), 6)
        if 135 <= plusAll(a) <= 141:
            result = sorted(a)
            return result
 
count = 0
a = random.sample(range(1, 45+1), 6)
a = sorted(a)
 
while True:
    b = lottoNumGen()
    b = sorted(b)
    count += 1
    if a == b:
        print(a, count)
        break

파이썬 언어를 모르시는 분들을 위해 위의 프로그램을 간략하게 설명하면 다음과 같습니다.

1. 1에서 45 사이의 랜덤한 번호 6개로 이루어진 수열 [a]를 만듭니다. 수열을 오름차순으로 정렬하여 순서를 맞춥니다. 수열의 각 숫자는 서로 겹치지 않습니다.
2. 수열 a와 모든 조건이 똑같지만, 각 숫자를 모두 합치면 135에서 141 사이에 있다는 조건을 추가한 수열 [b]를 만듭니다.
3. 수열 a와 b가 서로 일치하는지 비교합니다.
4. 수열 a와 b가 일치하지 않으면, 일치할 때까지 수열 b를 새로 만들어서 다시 비교합니다.
5. 수열 a와 b가 일치하면, 일치한 수열과 지금까지 수열 b를 몇 번 만들었는지 횟수를 출력하고 프로그램을 종료합니다.

여기서 문제입니다. 과연 이 프로그램은 정상적으로 종료될까요?

이런 식으로, 컴퓨터 프로그램이 언젠가 정상적으로 종료되는가 아니면 종료되지 않고 무한루프에 빠져 영원히 실행되는가를 판정하는 것을 정지 문제(halting problem)이라고 부릅니다. 조금 더 엄밀하게 말하자면, 정지 문제의 내용은 다음과 같습니다.

“임의의 프로그램 A가 주어졌을 때, A가 정상적으로 종료하는지 무한히 계속하는지를 결정하라.”

(출처 : http://scienceon.hani.co.kr/34696)

그럼, 과연 위에서 제가 작성한 프로그램을 실행시키면 언젠가는(비록 오랜 시간이 걸릴지라도) 결과값이 나올까요? 답은 [알 수 없다]입니다. 왜일까요? 제가 위에서 작성한 프로그램에는 이것과 관련된 아주 심각한 문제점이 하나 숨어 있습니다. 그것이 무엇인지는 한번 직접 생각해보시기 바랍니다. 아마도 프로그래밍을 배우신 분이시라면 보자마자 바로 알아챌 수 있으실 겁니다.

1936년에 ‘컴퓨터의 아버지’ 앨런 튜링은 위에서 언급한 정지 문제를 풀 수 있는 일반적인 방법(알고리즘)은 존재하지 않는다는 것을 증명하였습니다. 이게 무슨 소리냐 하면, 아무 프로그램이나 집어넣어서 이 프로그램이 정상적으로 종료된다고 보장할 수 있는 방법은 없다는 것입니다. 앨런 튜링의 증명 방법을 단순하게 설명하면 다음과 같습니다.

1. 정지 문제를 풀 수 있다고 가정한다. (귀류법)
2. 정지 문제를 풀 수 있는 절차(알고리즘)를 이용하여 프로그램 A를 만든다. 프로그램 A는 다음과 같은 프로그램이다.
   1. 프로그램 A는 다른 프로그램 B를 입력받는다.
   2. 만약 프로그램 B가 정상적으로 종료되는 프로그램이 맞으면, 프로그램 A는 무한루프에 빠져 응답을 멈춘다.
   3. 만약 프로그램 B가 무한루프에 빠져 응답을 멈추면, 프로그램 A는 정상적으로 종료된다.
3. 프로그램 A에 자기 자신(프로그램 A)을 입력한다.
4. 프로그램 A는 자기 자신이 정상적으로 종료된다고 해도, 무한루프에 빠진다고 해도 모순에 빠진다. 따라서 정지 문제는 판정할 수 없다(undecidable).

이 증명의 의미를 확장하면, [어떤 임의의 프로그램이 완전무결한지를 보증할 수 있는 방법은 없다]는 것이 됩니다. 다시 말해서, 어떤 프로그램에 버그가 전혀 없음을 증명할 수는 없다는 것이지요. 버그가 있다는 것은 보여주면 그만이지만, 버그가 전혀 없다는 것은 증명할 수가 없는 것입니다.

그럼, 컴퓨터가 자동으로 프로그램의 버그를 찾아내거나 하는 것은 완전히 불가능한 것일까요? 그렇지는 않습니다. 위에서 인용한 곳에는 이런 문장이 있군요. 제가 설명하는 것보다 이 문장을 인용하는 것이 더 적당할 것 같군요.

“종료 문제를 연구하는 소프트웨어공학자들은 가능한 모든 프로그램이 아닌 우리에게 가치가 있는 프로그램으로 문제의 범위를 제한한 뒤에 종료 문제에 대한 부분적인 해답을 얻는 것을 목표로 합니다. 임의의 모든 프로그램에 대해 종료 문제를 해결하는 것은 불가능하지만, 그럼에도 불구하고 상당수의 프로그램에 대해서는 해결이 가능하다는 뜻입니다 (마찬가지로, 완벽한 백신은 이론적으로 불가능하지만 매우 믿을 만한 백신은 충분히 가능하다는 희소식이기도 합니다). 이들이 연구하는 기술을 자동종료 증명(Automated Termination Proof)이라고 합니다. 주어진 소프트웨어가 언제나 정상적으로 종료하는지를 자동으로 증명하는 도구를 만드는 것입니다.”

그럼 여기서, 제가 위에서 작성한 프로그램이 어째서 결과값이 나올지 안 나올지를 알 수 없는지 혹시 눈치채지 못하신 분들을 위해 이유를 공개하겠습니다.

만약 수열 a의 값이 수열 b처럼 총합의 범위가 135에서 141 사이에 있으면 확률에 의해 언젠가는 결과값이 나올 수 있을 것입니다. 그런데 수열 a의 총합의 범위가 135에서 141 사이를 벗어나 있으면, 아무리 수열 b를 생성해도 수열 a와 b가 일치하는 일은 일어날 수가 없습니다. 수열 b는 총합의 범위가 135에서 141 사이라는 제약조건이 있으니까요. 문제는 수열 a가 어떤 값으로 생성될지는 완전히 랜덤이라는 점입니다. 따라서 위 프로그램을 실행시켜보기 전에는 위 프로그램이 정상적으로 종료될지 아니면 무한루프에 빠질지 알 수가 없지요.

이상, 오늘의 뻘글이었습니다.

p.s.
이 글의 내용이 재미있으셨다면, 다음 글도 한번 읽어보세요.
http://www.joysf.com/4602163