컴퓨터는 모든 것을 해결할 수 있을까? (halting problem)

이 글의 제목처럼 컴퓨터가 모든 문제를 해결할 수 있는지, 즉 답을 낼 수 없는 문제는 없는지 알아보자.

---

 

예를 들어 컴퓨터A가 존재한다고 가정하자.

이 컴퓨터는 똑똑해서 어떤 복잡한 수식도 해결할 수 있다.

즉 수식을 입력받아 그 결과를 출력한다.

 

이번에는 더 복잡한 일을 하는 컴퓨터도 생각해보자.

새로운 컴퓨터C는 바둑의 알파고처럼 체스판의 이미지를 입력받아 다음 번에 둬야할 수를 알려준다.

 

이 두 컴퓨터는 올바른 타입의 입력이 주어지지 않는다면 멈춰버린다.

위 예시에서는 컴퓨터A에게 체스판을 주거나 컴퓨터C에게 수식을 입력하는 상황이다.

 

이렇듯 입력만 올바르다면 컴퓨터는 복잡한 질문에 대해서도 옳은 결과를 제시할 수 있다.

하지만 컴퓨터는 모든 것을 해결할 수 있을까?

 

---

 

이 문제를 해결하기 위해 새로운 컴퓨터H를 생각하자.

이 컴퓨터는 입력으로 두 가지를 받는다.

하나는 '어떤 컴퓨터의 설계도'이고, 다른 하나는 그 컴퓨터에 입력으로 주어질 문제이다.

컴퓨터H는 설계도를 바탕으로 해당 컴퓨터가 그 문제를 받았을 때 멈출지 안멈출지 결과를 내놓는다.

컴퓨터H의 동작을 이해하기 위해 예시를 몇가지 들어보면,

컴퓨터A의 설계도와 수식을 입력으로 준다면 컴퓨터H는 '정상작동' 이라는 결과를 출력할 것이다.

만약 컴퓨터C의 설계도와 수식을 입력으로 받는다면, '멈춤' 이라는 결과를 출력할 것이다.

 

이제 정말 단순한 컴퓨터 두 개를 더 생각해보자.

컴퓨터P는 입력을 복사해 두 개로 만들어 출력한다.

거꾸로 행동하는 컴퓨터N은 '멈춤'이라는 입력을 받으면 멈추지 않고 GOOD이라는 단어를 출력하고

'정상작동'을 입력으로 받으면 멈춰버린다.

 

이제 컴퓨터P,H,N을 순서대로 연결한 컴퓨터를 X라고 하자.

이제 이 문제에 답을 내기 위한 컴퓨터들은 모두 소개가 되었다.

 

---

컴퓨터X의 입력으로 자신의 설계도를 넣으면 어떻게 될까?

먼저 컴퓨터P를 거쳐 컴퓨터H에게 자신의 설계도 2개가 입력으로 들어갈 것이다.

 

컴퓨터H의 결과가 '정상작동'과 '멈춤' 중에 무었일지는 모르기 때문에 두 가지 경우를 모두 생각해보자.

 

1. 결과가 '정상작동'일 경우

컴퓨터N은 '정상작동'을 입력으로 받았으므로 멈춰버린다.

결국 이 경우에는 컴퓨터X는 자신의 설계도를 입력으로 받으면 멈추게 된다.

 

그러나 가정에 따라 X의 설계도 2개를 입력으로 받은 H는,

X가 자신의 설계도를 입력으로 받았을 때 '정상작동'할 것이라고 얘기했으므로 모순이 된다.

 

2. 결과가 '멈춤'일 경우

그럼 이번에는 H가 '멈춤'이라는 결과를 출력했다고 가정하자.

그렇다면 컴퓨터N은 GOOD이라는 단어를 출력할 것이다.

즉 X에 자신의 설계도를 넣었을 경우 정상작동 하여 GOOD이라는 결과가 나온다.

하지만 H는 멈출 것이라고 했으므로 이 경우도 모순이다.

 

따라서 이런 컴퓨터H는 존재할 수 없다는 것이 논리적으로 증명되었다.