튜링 기계

튜링 기계는 긴 테이프에 기록된 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 장치이다. 1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 고안하고, 자동을 뜻하는 'automatic'의 앞 글자를 따서 a-기계라는 이름을 붙였다. 이 장치는 나중에 창시자의 이름을 따서 튜링 기계라 불리게 되었다. 튜링 기계는 상당히 간단한 구조를 가지지만, 적절한 규칙과 기호를 입력하면 일반적인 컴퓨터의 알고리즘을 모두 수행할 수 있다.

튜링 기계는 다음과 같은 핵심 요소로 구성된다.

• 테이프: 무한한 길이를 가지며, 하나의 기호를 인쇄할 수 있는 정사각형 셀들로 나뉘어 있다. 이는 기계의 저장 공간 역할을 한다.
• 읽기-쓰기 헤드: 테이프 위를 앞뒤로 움직이며 각 셀에 적힌 기호를 읽거나 새로운 기호를 쓸 수 있다.
• 상태 기록기: 기계의 현재 상태를 저장하며, 읽힌 기호와 현재 상태에 따라 기계가 다음에 할 행동을 결정한다.

기계는 매 단계마다 헤드가 위치한 셀의 기호를 읽고, 정해진 규칙에 따라 기호를 수정하거나 테이프를 왼쪽 또는 오른쪽으로 한 칸 이동시킨다. 이러한 단순한 명령어들의 집합을 통해 복잡한 논리 연산과 계산을 처리한다.

튜링 기계는 20세기 초 수학자 다비트 힐베르트가 제시한 '결정성 문제'를 해결하는 과정에서 탄생하였다. 튜링은 1936년 발표한 논문 〈계산 가능한 수와 결정성 문제에의 응용〉에서 이 모델을 처음 소개하였다. 당시 튜링은 수학적 증명 과정을 몇 가지 추론 규칙의 반복으로 보고, 이를 기계적으로 수행할 수 있는 논리적 장치를 구상하였다.

튜링 기계는 현대 컴퓨터의 CPU 기능을 설명하는 데 매우 유용하며, 이론 컴퓨터 과학의 핵심적인 개념이다. 앨런 튜링은 이 모델을 바탕으로 1943년 제2차 세계대전 당시 독일군의 암호 기계인 에니그마를 해독하기 위한 연산 기계 콜로서스를 제작하는 데 기여하였다. 이는 이진수 기반 컴퓨터의 기초를 마련한 중요한 업적으로 평가받으며, 튜링이 '컴퓨터 과학의 아버지'로 불리는 근거가 되었다.