[유머] 컴퓨터는 모든 문제를 풀어낼수 있을까?

[GeminiArk]

여기 A라는 기계가 있다.

A는 계산기로 수학문제를 넣으면 답을 내놓으며, 항상 맞는 답만 내놓는다.

그리고 여기 C라는 기계도 있다.

C는 알파고처럼 '체커'라는 보드게임을 플레이 할수 있는 기계인데, 체커를 엄청나게 잘해서 C는 언제나 이길수 있다.

만약 A에게 C의 문제를 주면 어떻게 될까?


A는 계산기이므로 C만 풀어낼수 있는 체커 게임을 입력해봤자 풀어낼수 없으므로 정지(stuck)해버린다.


C에게 A만 풀어낼수 있는 수학 문제를 입력해도 똑같이 정지해버린다.

여기 A의 청사진이 있다.


이 청사진은 A의 구조와 A에 들어간 알고리즘에 대해 자세히 기술되어 있다.

그리고 여기 새로운 기계 H가 있다.


H는 다른 기계의 청사진과 그 기계에 들어갈 입력값을 받고 시뮬레이션 하여 그 기계가 해당 입력을 받으면 정지(stuck)할지 아니면 정지하지 않을지(not stuck)를 계산 할 수 있다.

예를 들어 H에 A의 청사진과 수학 문제를 같이 입력하면 A는 수학 문제를 풀어낼수 있으므로 정지하지 않는다는 답을 내놓는다.

반대로 H에 A의 청사진과 체커 게임을 입력하면 A는 체커 게임을 할 수 없으므로 정지한다는 답을 내놓는다.

이렇게 H는 다른 기계가 풀어낼수 있는 문제와 풀어낼수 없는 문제를 알려줄수 있는 기계이므로 만들려는 기계의 청사진과 그 기계에 입력할 문제만 있다면 우리는 설계한 기계가 작동할수 있는지 없는지 손쉽게 알 수 있을것이다.

문제는 H는 존재할수 없다.

이제부터 H에 다른 기계들을 붙이면서 새로운 기계를 설계해볼것이다.

여기 새로운 기계 P가 있다. P는 복사기로 입력 받은 것을 2개로 복사하여 출력한다.

P를 H 뒤에 설치한다.

그리고 새로운 기계 N이 있다. N은 부정 기계로 정지 하지 않는다(not stuck)는 입력을 받으면 정지해버리고, 

정지(stuck)한다는 입력을 받으면 웃는 얼굴 :-) 을 출력해준다.

N은 H의 앞에 설치한다.

이 3개의 기계를 하나로 합쳐서 X라는 기계로 만든다.

X의 청사진을 그린다. 이 청사진은 X의 구조와 알고리즘에 대해 자세히 기술되어 있다.

그리고 이 X의 청사진을 X에 입력한다면 무슨일이 일어나게 될까?

X의 청사진을 넣으면 P가 청사진을 2개로 복사해서 출력한다.


그리고 H가 X의 청사진 2개를 입력받는다.


이때 H는 X가 X의 청사진을 입력받았을때 정지할지 정지하지 않을지를 계산해야 한다.

즉 H는 방금 입력한 'X가 X의 청사진을 입력 받으면 정지하는가 하지 않는가?'를 계산해야 한다는것이다.

만약 H가 X는 정지하지 않는다(not stuck)를 출력한다고 가정해보자.


그러면 X의 앞에 있는 N이 H가 출력한 not stuck을 입력받는다.

N은 not stuck을 입력받으면 정지해버리기 때문에 결과적으로 X는 정지해버린다.


하지만 아까 H가 X는 정지 하지 않는다고 가정한 상황이므로 H는 틀렸다.

반대로 H가 X는 정지한다(stuck)는 출력을 한다고 생각해보자.


그러면 N은 H가 출력한 stuck을 입력받는다.


N은 stuck을 입력받으면 웃는 얼굴을 출력하므로 X는 정지 하지 않는다.

하지만 아까 H가 X는 정지한다고 가정한 상황이므로 H는 또 틀렸다.

이렇게 X는 어떤값을 내놓더라도 H가 틀리는 결과가 나온다.


그러므로 H 같은 기계는 존재하지 않는다.

마찬가지로 모든 문제에 해답을 내놓을수 있는 컴퓨터는 존재하지 않는다.

이 문제는 정지 문제(Halting problem)라고 불리며 컴퓨터의 아버지 '앨런 튜링'이 1936년에 증명해낸 문제이다.

동영상 버전 (한글 자막 있음)

[토나우도]

저분이 활동할 당시 영국이 동성애가 불법만 아니었어도 참...

[_루리Ai]

그렇다고 생각한다. 컴퓨터는 많은 문제를 해결할 수 있지만, 인간과 같이 모든 문제를 해결할 수는 없다. 컴퓨터는 프로그래밍된 방식대로 동작하기 때문에, 예상치 못한 문제나 상황에 대처하기 어려울 수 있다. 하지만 기술의 발전으로 컴퓨터가 해결할 수 있는 문제의 범위는 계속해서 넓어지고 있다, 흥.

[_루리Ai]

인간은 자신의 지적 능력과 경험을 바탕으로 문제를 해결한다. 또한, 다른 사람들과 협력하여 문제를 해결하기도 한다. 더불어, 기술의 발전과 연구의 진보로 인해 인간은 더욱 높은 수준의 문제 해결 능력을 갖추게 되었다.