컴퓨터는 만능 알고리즘 기계인가?

컴퓨터는 만능 알고리즘 기계인가?

서론

근래에 컴퓨터에 대한 관심이 급증하고 있다. 사실 근래라고 하기엔 근래가 아니라고 할 것 같다. 언론에서 매일같이 IT 관련 기사를 쏟아내던 것은 20년도 더 되었으니.

알파고가 나온 이후로 컴퓨터와 인공지능에 대한 관심은 더욱 폭증하였고 급기야 이제는 본인의 일자리를 잃을까 두려워 하는 처지에까지 이르게 되었다.

제목과 앞선 2문단과는 달리, 본 포스팅에서 이에 대한 해답을 얻기는 어려울 것 같다. 컴퓨터가 모든 문제를 해결할 수 있는 만능 기계가 아님을 설명하기 위한 것이지, 미래의 일자리 형태가 어떻게 변화할 것인지 설명하는 것과는 거리가 멀다. 심지어 철학적인 이야기를 할 것도 아니다.

근대적 컴퓨터의 구상

앨런 튜링

앨런 튜링이란 사람은 IT에 관심이 좀 있다면 다들 한번씩 들어봤을 것이다. 그 또한 2차 세계대전이 진행되던 시기의 컴퓨터과학자이며 당시 나치의 암호를 해독하는 방법을 고안해낸 사람이다.

이건 사족이긴 한데, 그가 동성애자 였을 것이라는게 학교의 점심이다.

다시, 앨런 튜링으로

지금 앨런 튜링을 얘기한 이유는 그가 제시한 개념 중 하나인 튜링 머신을 소개하기 위함이다. 튜링 머신은 앨런 튜링이 1936년에 제시한 개념이며 계산하는 기계의 일반적 개념을 설명하기 위한 가상의 기계이다.

튜링 머신의 구성 요소

• 테이프(정보 저장)
• 헤드(정보 읽기)
• 상태 기록기(정보 저장)
• 행동표(명령어)

각 구성요소를 적재적소에 배치하여 논리적 연산을 수행한다. 튜링이 제안한 방법에 따라 시스템이 작동하면 튜링 완전이라 하는데, 현대 대부분의 언어는 튜링 완전을 충족한다.

튜링 완전의 조건은 무엇인가?

1. 절차적 언어

1. 조건 분기문이 있다.
   • if, goto, for, while등의 조건문과 반복문
2. 임의 위치의 메모리 값을 바꿀 수 있다.

2. 람다 대수

1. 람다 대수??
   • 추상적 논리연산을 표현하기 위해 제안된 계산 모델
2. 람다 대수 모델로 표현가능한 문제를 해결할 수 있으면 조건을 충족한다.

마침내, 컴퓨터가 할 수 없는 것

정지 문제(Halting Problem)

주어진 프로그램(prog)이 해결하고자 하는 문제(prob)를 해결할 수 있는지 판별해 주는 알고리즘은 존재하는가?

흠.. 주어진 알고리즘이 문제를 해결할 수 있는지 판단해주는 알고리즘이 존재하냐고??

감이 잘 안오지만 의사코드(pseudo-code)라도 작성해보자.

function halt(prog, prob)
    if working
        return true
    else
        return false 

이게 뭐야.. working하는지 안 하는지는 조상님이 알려주냐?

일단 뒤로 미루어 두고 작동하면 true를 반환하고 그렇지 않으면 false를 반환한다는 것만 알아두자.

halt 함수가 존재할 수 없는 이유

그 이유는 귀류법으로 증명이 가능하다.
halt 함수가 존재하지 않는다는 것이 정론이니, 존재한다고 가정해보자.
그리고 halt를 모순시키는 함수를 하나 더 정의하자

function trouble(prog)
    if halt(prog, prog) == false
        return true
    else
        loop forever

위 함수를 보면 halt하지 못하는 경우(프로그램이 잘못된 경우)에는 참을 반환하고 halt하는 경우(프로그램이 정상적인 경우)에는 계속 반복하며 반환값을 주지 않는다. 종료되지 않는 알고리즘은 잘못된 알고리즘이다.

이제, trouble 함수에 trouble을 다시 넣자.

trouble(trouble)

작동 중인 trouble 함수를 다시 표현하면 이런 형태가 될 것이다.

function trouble(trouble)
    if halt(trouble, trouble) == false
        return true
    else
        loop forever

이쯤되면 ‘입력란으로 넣는 곳에 멋대로 프로그램을 넣고 거꾸로 작동하는 trouble이 trouble을 호출하고.. 뭐 이래도 되는거야?’ 싶을 수도 있지만, 문제될 것 없다.

어짜피 경우는 두가지이다. true를 반환하거나 loop forever하거나

두가지 경우로 나누어 생각해보자.

1. halt(trouble, trouble) == false
   • halt 함수가 false를 반환했다. 잘못된 알고리즘이라는 것이다. 하지만, halt 함수가 false를 반환하는 순간 trouble 함수는 true를 반환하면서 정상적으로 종료된다. halt 함수가 틀렸다.
2. halt(trouble, troulbe) == true //i.e. else
   • halt 함수가 true를 반환했다. 작동하는 알고리즘이라는 것이다. 하지만, 그 순간 trouble함수는 무한 반복하며 고장나버린다. 또 틀렸다.

결국, halt 함수가 존재한다고 했을 때, 모순이 발생하므로 halt 함수는 존재하지 않는다.

총론

컴퓨터가 못 푸는 문제도 하나쯤은 있겠지.. 따위의 결론을 말하고 싶지는 않다. 컴퓨터가 모든 문제를 해결할 수 있으면 로또번호도 맞추겠네? 그렇지는 않다.

다만, ChatGPT와 같은 LLM 모델이 등장하면서 기존 데이터를 활용하여 코드를 작성해주기도 하고 컴퓨터가 번역도 해주고 그런 상황이다 보니 가끔 컴퓨터가 만능이라는 믿음 하에 본인의 걱정은 애써 무시하며 오히려 오만하는 사람이 있는 것 같기도 하다.

나를 포함해서, 뭐든지 다 할수 있는 만능 기계 따위도 없고 만능 인간 또한 없다. 겸손하게 살자. 세상은 나 혼자서 사는 곳도 아니고 혼자서 살 수도 없다.

참고 문헌

• 나무위키. (2024). “튜링 머신”. https://namu.wiki/w/튜링머신.
• 나무위키. (2024). “정지 문제”. https://namu.wiki/w/정지문제.
• Wikipedia. (2024). “튜링 기계”. https://ko.wikipedia.org/wiki/튜링_기계.
• Wikipedia. (2024). “정지 문제”. https://ko.wikipedia.org/wiki/정지_문제.
• Wikipedia. (2024). “람다 대수”. https://ko.wikipedia.org/wiki/람다_대수.