최근에 컴퓨터의 아버지라고 불리는 앨런튜링을 주인공으로 하는 영화가 극장에서 인기를 끌고 있다. 사실 튜링은 처음부터 지금의 컴퓨터와 같은 것을 만들려고 했던 것은 아니었다.

독일 수학자 힐버트는 1928년 세계적인 수학자 회의에서 23개의 인류가 해결해야할 문제를 거론하였다. 그 중에 하나는 ‘원칙적으로 수학의 모든 문제를 순서대로 해결할 수 있는 일반적인 기계적 절차가 있는가?’라는 문제를 제기했다. 조금 더 설명해 보면 어떠한 문제이던지 그것을 해결하는 기계적 절차 또는 순서가 존재하느냐는 것이다. 예를 들어 보자.

가까운 미래의 주가를 예측하는 기계적인 또는 일반적인 순서가 존재하느냐? 또는 나에게 내일 무슨 일이 일어날지 예측할 수 있는가? 쉽게는 2시간 후의 날씨는 어떻게 될 것 인가? 등에 대한 정답을 구하는 기계적인 순서가 있느냐에 대한 질문이라고 할 수 있다.

이 대목에서 중요한 것은 순차적, 기계적이라는 것이다. 이 얼마나 놀라운 발상인가? 어떠한 문제이던지 해결책이 순서대로만 하면 해결된다니! 주가를 예측하는 순서가 있다면 당장 부자가 될 수 있을 것이다. 그러나 그런 순서를 찾기는 쉽지 않을 것이다. 문제에 대한 해결책에 대한 해결 순서 또는 절차가 존재고, 그 절차를 처리하는 기계가 있다면 기계에 의해서도 해결할 수 있게 된다.

앨런 튜링은 힐버트의 문제를 해결하기 위해 튜링머신이라는 가상의 기계를 고안하였다. 이 가상의 기계는 놀랍게도 현대의 컴퓨터와 크게 다르지 않았다. 튜링에게 컴퓨터란 문제를 푸는 기계적 순서를 실행하는 기계인 것이다. 문제를 해결하는 기계적인 순서 또는 절차가 존재한다면 계산 가능이라고 부르고 그렇지 않으면 계산 불가능이라고 부른다. 또한 계산 가능과 불가능을 연구하는 학문을 계산이론(Computing Theory)로 한다. 그리고 문제해결을 위한 기계적 절차를 고안하고 실제 실행에 관한 것을 컴퓨팅(Computing) 이라고 한다. 컴퓨팅(Computing)을 실제 수행하는 기계가 컴퓨터(Computer) 인 것이다.

튜링이 고안한 튜링 머신에 대해 조금 더 자세히 알아보자 튜링 머신은 데이터가 기록되어 있는 테이프와 이것을 읽는 입출력 헤드, 입출력 헤드를 제어하는 제어 장치로 되어 있다. 테이프는 길이는 무한대인데, 각각의 칸에 기록된 데이터는 오로지 한 개의 기호를 갖고 있거나 아니면 비어 있다. 그러나 테이프에 기록된 기호의 수는 유한하다.

[그림 ] 튜링 머신의 구조

간단한 예를 통해 튜링머신을 알아보도록 하자. 일반적으로 컴퓨터에서 문자열 더하면 합쳐지는 연산을 수행하게 된다. 그러므로 “111”+“1”=“1111” 이 된다. 문자열 합치는 문제를 튜링머신을 통해 해결하는 방법을 살펴보자. 해결해야 할 문제를 테이프를 통해서 알아보면 아래 그림처럼 “111” 이 기록된 테이프가 있을 때 문자열 1을 더해 “111”을 만들면 된다.

이 문제를 해결하기 위해 튜링 머신은 다음과 같은 기능을 가지고 있다(현대적 용어로 프로그램 되어 있어야 한다).

제어장치의 상태- {go, stop}
테이프에 저장되는 기호 – {“1”, “ ”}
기계의 초기 상태 – go
기계가 멈추는 상태 – stop
기계의 동작 규칙 – {go, “ ”, stop, next}, {go, 1, go,1,next}

기계의 동작 규칙을 설명 하면 {go, 1,go,1,next} 의 경우는 현재 상태가 go이고 테이프에 1이 있으면 상태는 go로 하고 테이프에 1을 쓰고, 다음칸으로 이동한다.

{go, “ ”, stop, next} 의 경우는 현재 상태가 go 이고 테이프가 “ ” 이면 상태를 stop 으로 바꾸고 다음 칸으로 이동한다. 즉 기계의 동작이 중지된다.

다음 그림은 튜링 기계의 초기 상태는 Go 이고 헤드는 첫 번째 칸에 위치한다. 현재 상태가 go 이고 테이프 칸의 값이 1이므로 동작 규칙 {go, 1,go,1,next} 이 적용된다.

그래서 튜링 기계의 다음 상태는 아래 그림처럼 된다. 앞과 같은 상태이므로 동작 규칙 {go, 1,go,1,next} 이 적용된다.

그 결과 아래 그림처럼 됩니다. 이 상태 역시 앞과 같은 상태이므로 동작 규칙 {go, 1,go,1,next} 이 적용된다.

그 결과 아래 그림처럼 됩니다. 이 상태는 앞과는 다른 경우 이므로 동작규칙 {go, “ ”, stop, next} 가 적용됩니다. 그러므로 상태는 go에서 stop 으로 되고 1을 쓰고 다음칸으로 가게 됩니다.

결과적으로 아래 그림처럼 1이 추가되고 튜링머신은 멈추게 됩니다.

위의 예와 달리 다양한 상태와 기호를 가질 수 있는 기계를 범용튜링 머신이라고 부르며 이것은 현대의 컴퓨터를 만드는 아이디어가 되었다. 여기서 테이프는 메모리이고, 제어장치는 CPU 가 되고 입출력 헤드는 메모리 제어 유닛으로 바꾸면 컴퓨터와 같게 된다.

앞에서 언급한 “모든 문제를 순서대로 해결할 수 있는 일반적인 기계적 절차” 는 간단하게 컴퓨터 알고리즘이라고 부른다. 컴퓨터가 어떤 동작을 하고 결과를 만들어내는 것은 그것을 처리하는 알고리즘이 있기 때문이다. 그러므로 컴퓨터를 통해 어떤 문제를 해결하려면 그에 맞는 알고리즘을 고안해야한다. 이 알고리즘을 컴퓨터에 넣는 것이 프로그래밍이다.

이제는 다시 컴퓨터가 없는 세상으로 돌아가는 것을 상상하기 어려운 일이다. 컴퓨터는 현대인에게 일상생활의 여러 문제를 해결하는 도구로 완전히 자리 잡았다고 할 수 있다. 그러나 대부분의 사람들은 남이 만들어 놓은 알고리즘으로 자신의 문제를 처리한다. 최근에 스마트폰에 들어 있는 운영체제를 만든 회사가 사용자의 데이터 수집 알고리즘을 넣은 것이 문제가 된 적이 있다. 데이터 수집 알고리즘에 의해 모여진 데이터는 그 자체가 큰 가치를 지닌 것이라 할 수 있다. 또한 이에 대한 처리 방법, 또한 역시 큰 가치를 지니고 있다. 이것이 문제의 핵심이라고 할 수 있다. 자신도 모르게 스마트폰에서 모아진 데이터는 다른 사람이 돈을 버는데 사용될 수도 있기 때문이다. 데이터를 모우고 그것을 처리하는 알고리즘이 새로운 가치를 만들고 그 가치에 따라 상상하기 힘든 결과를 가져오는 경우가 종종 있다. 이러한 일은 남이 만들어놓은 알고리즘으로 사는 사람들은 어쩔 수 없이 겪어야 하는 일이라고 외면할 수 도 있지만 이제는 우리도 남이 만들어 놓은 알고리즘 안에서 나와 우리의 알고리즘을 창조하는 사람들이 많이 나왔으면 좋겠다.