MIU- 체계와 Computability

글자 M, I, U를 임의로 배열할 수 있는 형식 체계가 있다고 하자. 예를들어 MI, MIU, MIIU, UMII 등등이 이 형식 체계 내에 존재할 것이다. 이 형식 체계에 다음과 같은 규칙이 있다고 하자.

1. 마지막 글자가 I인 경우에는 그 끝에 U를 추가할 수 있다. (예, MI -> MIU)
2. Mx가 있다면 Mxx를 만들 수 있다. 여기서 x는 임의의 길이의 글자이다. (예, MIU -> MIUIU, MU->MUU)
3. 만약 III가 나타나면 이를 U로 바꿀 수 있다. (예, MIII -> MU, UMIIIMU-> UMUMU)
4. 만약 UU가 나타나면 이를 삭제 할 수 있다. (예, MUU->M, MUUUIII-> MUIII)

이 규칙들은 무한히 반복하여 정의 될 수 있다. 여기서 과제는 특정 문자열에서 다른 문자열을 이끌어 낼 수 있는지를 판별하는 것이다. 예를들어 MI에서 위의 규칙들을 임의 순서로 적용해서 MU를 만들어 낼 수 있을까? (한번 해보세요) 컴퓨터에게 이러한 일을 할 수 있는 프로그램을 짜려고 한다. 다음과 같은 알고리즘을 보자

1. 초기 문자열을 set에 넣는다.
2. 만약 set에 결과 문자열이 있으면 만들 수 있는 것이다.
3. set에 있는 문자열들에 각각 1,2,3,4를 적용하여 적용된 문자열을 집어 넣는다.
4. 2번으로 돌아간다.

이 알고리즘의 문제는 만약 규칙을 적용해서 결과 문자열을 만들어 낼 수 있으면 결과가 나오지만 만들어 낼 수 없는 경우에는 무한히 계속된다는 점이다. 이 과제를 사람한테 시켰을때에는 어떨까? 앞에 주어진 MI에서 MU를 이끌어 내는 과제를 해보신 분은 느끼셨겠지만 (답은 이끌어 낼 수 없다이다. ^^;;) 사람은 이를 적용하면서 규칙에 관한 규칙 (메타 규칙)을 이끌어 낸다고 한다. 쉬운과제를 생각해보자. MI에서 U를 이끌어 낼 수 있을까? 아마 컴퓨터는 위의 알고리즘을 무한히 반복할 것이다. 하지만 사람의 경우 위의 규칙 만으로는 맨 앞의 M을 제거할 수 없다는 것을 쉽게 깨닫고 이것이 불가능함을 말할 것이다. 이것이 알고리즘의 문제일까? 만약 컴퓨터도 위와 같은 메타 규칙을 이해하는 프로그램을 짠다면 이를 계산해 낼 수 있지 않을까?

답은 그런 알고리즘을 짤 수 없다이다. 왜? 이 문제는 컴퓨터 과학에서 Halting Problem이라는 문제로 증명되었다. 간단하게 얘기하면 어떤 프로그램이 무한히 동작할지 그렇지 않을지는 그 프로그램을 직접 돌려보기 전까지는 알 수 없다는 것이다.

Step 1. Halting Problem을 해결하는 프로그램 Q가 있다고 하자. Q는 다음과 같은 결과 값을 지닌다.

Q(P, x) return "Halt" when P(x) halts
Q(P, x) return "Does not Halt" when P(x) does not halts

Step 2. Q를 이용해서 D라는 프로그램을 작성했다고 하자. D(P)는 아래와 같은 결과값을 지닌다.

D(P) return "run forever" when Q(P, P) halts
D(P) return "halt" when Q(P, P) does not halts

여기서 Q를 풀어내면 D(P)는 아래와 같은 결과를 지닌다.

D(P) return "halt" when P(P) does not halts
D(P) return "run forever" when P(P) halts

Step 3. 여기서 P는 임의의 프로그램 프로그램이므로 D 자신일 수도 있다. 그러면 P에 D를 대입해보자.

D(D) return "halt" when D(D) does not halts
D(D) return "run forever" when D(D) halts

매우 재미있는 결과가 나온다. D(D)가 멈추지 않을 경우에는 "halt"가 나오고 D(D)가 멈출 경우에는 "run forever"가 나와야 한다. 물론 이는 모순이다. 따라서 Step 1에서와 같은 프로그램 Q는 작성할 수가 없다. 이를 앞에 알고리즘에 적용한다면 MI에서 MU를 이끌어 낼 수 있는지 없는지를 판별하는 프로그램은 작성할 수 없다는 것을 의미한다.

과연 이러한 사실로부터 인공지능이 불가능하다는 논리를 이끌어 낼 수 있을까?

참고

괴델, 에셔, 바흐: http://www.aladdin.co.kr/shop/wproduct.aspx?ISBN=897291231X&partner=egloos
Halting Problem: http://en.wikipedia.org/wiki/Halting_problem