튜링 기계는 계산을 가장 단순한 규칙으로 분해해 보여 주는 추상적 계산 장치이다. 이 문서는 그 형식적 구조와 계산 이론에서의 의미를 정리한다.[2]
1. 개요
튜링 기계는 앨런 튜링이 1936년 전후에 제안한 추상적 계산 장치이다.[2] 이 모델은 계산을 수행하는 절차를 기호의 읽기, 쓰기, 이동과 상태 변화로 나누어 표현한다. 어떤 문제가 계산 가능한지, 그리고 계산 가능한 문제라도 어떤 방식으로 처리되는지를 살피는 데 널리 쓰인다.[2][3] 오늘날의 디지털 컴퓨터와 수학적으로 같은 계산 능력을 가진 기준 모형으로도 이해된다.[3]
과거에 ‘컴퓨터’라는 말이 사람을 가리키던 시기에도, 튜링의 모델은 계산을 손기술이 아니라 절차와 규칙의 문제로 다시 정의했다.[2] 이 점 때문에 튜링 기계는 알고리즘을 설명하는 가장 기본적인 틀 가운데 하나가 되었다.[2]
2. 형식적 정의
튜링 기계는 유한한 상태 집합, 테이프에 적을 수 있는 기호 집합, 시작 상태, 그리고 상태와 기호의 조합에 따라 다음 행동을 정하는 전이 규칙으로 이루어진다.[4] 입력은 테이프의 일부 칸에 적히고, 나머지 칸은 비어 있는 기호로 본다. 기계는 현재 칸의 기호를 읽은 뒤 새 기호를 쓰고, 왼쪽이나 오른쪽으로 한 칸 이동하며, 다음 상태로 옮겨 간다.[4]
이 구조는 복잡한 계산도 몇 가지 단순한 동작의 반복으로 바꿔 보여 준다. 그래서 튜링 기계는 계산 이론에서 알고리즘의 형식을 엄밀하게 적는 데 자주 사용된다.[2][3] 또한 상태 수가 제한된 다른 모델과 비교할 때, 테이프를 통해 더 긴 기억을 다룰 수 있다는 점이 특징이다.[3]
3. 작동 원리
한 단계의 계산은 현재 상태와 현재 기호를 함께 보고 결정된다. 예를 들어 어떤 상태에서 특정 기호를 읽으면, 기계는 그 칸의 기호를 다른 기호로 바꾸고, 헤드를 한 칸 옮긴 뒤, 미리 정해 둔 새 상태로 들어간다.[4] 같은 규칙이 반복되다가 더 이상 적용할 규칙이 없으면 계산이 끝난다. 이런 멈춤 여부는 어떤 문제가 실제로 풀릴 수 있는지를 따질 때 중요한 기준이 된다.[2]
계산 과정을 그림으로 나타낼 때는 보통 시간 순서에 따라 테이프의 내용, 현재 상태, 헤드 위치를 나란히 적는다. 이렇게 보면 하나의 계산이 길게 이어지는 규칙적 변환이라는 점이 분명해진다. 튜링 기계는 겉으로는 단순하지만, 그 단순함 때문에 오히려 계산의 본질을 선명하게 드러낸다.[3]
4. 보편 튜링 기계
보편 튜링 기계는 다른 튜링 기계의 설명과 입력을 함께 받아 그 기계를 흉내 내는 장치이다.[3] 즉, 어떤 특정 계산만 하는 기계가 아니라, 테이프에 적힌 규칙 설명을 읽고 그에 맞는 계산을 실행한다. 이 개념은 프로그램과 데이터를 분리해 이해하는 현대적 계산 방식의 핵심을 보여 준다.[3]
보편 기계의 의미는 매우 크다. 하나의 장치가 다른 장치의 행동을 일반적으로 모사할 수 있다는 사실은, 계산이 특정 하드웨어의 기능보다 더 추상적인 절차라는 점을 드러낸다. 이 아이디어는 현대 디지털 컴퓨터가 여러 프로그램을 실행하는 방식과 수학적으로 대응한다.[3]
5. 계산 이론에서의 역할
튜링 기계는 계산 복잡도 이론과 계산-가능성의 중심 모형이다.[3] 어떤 문제가 풀리는지, 어떤 문제는 원리적으로 풀리지 않는지, 그리고 풀리더라도 얼마나 많은 자원이 드는지를 따질 때 이 모델이 기준점 역할을 한다.[2][3] 대표적으로 멈춤 문제처럼, 모든 입력에 대해 정답을 판단할 수 없는 문제가 존재함을 보이는 데 쓰인다.[2]
이 모델이 중요한 이유는 단지 오래되었기 때문이 아니다. 튜링 기계는 계산의 절차를 최소한의 구조로 추상화해, 서로 다른 계산 장치 사이의 공통된 개념을 비교할 수 있게 한다. 그래서 알고리즘의 정의, 계산 가능한 함수, 효율성의 비교 같은 주제를 다룰 때 지금도 기본 언어로 쓰인다.[2][3]
6. 한계와 해석
튜링 기계는 실제 기계를 정밀하게 모사하려는 장치가 아니다. 전기 신호의 잡음, 실제 메모리 장치의 물리적 제약, 병렬 처리 같은 요소는 거의 다 빠져 있다.[3] 그러나 바로 그 단순화 덕분에 계산의 본질만 남기고 논의할 수 있다. 즉, 이 모델은 실제 공학 장비의 설계도라기보다 계산을 설명하는 수학적 기준에 가깝다.[2]
이 점을 구분하면 튜링 기계의 가치가 더 분명해진다. 어떤 계산이 가능한지에 대한 판단은 물리 장치의 종류와 무관한 수준에서 정리되어야 하며, 튜링 기계는 그 공통 기준을 제공한다.[2][3] 따라서 이 모델은 컴퓨터 과학의 역사적 출발점이자, 지금도 이론적 논의를 정리하는 기초 틀로 남아 있다.
7. 역사적 배경 및 의의
튜링은 1936년의 논문에서 계산을 절차적으로 정의하려는 시도를 전개했고, 그 과정에서 오늘날 튜링 기계로 불리는 모형이 정립되었다.[2] 당시에는 계산의 범위를 사람의 손계산과 기계적 절차까지 포함해 넓게 생각했지만, 튜링은 이를 엄밀한 수학 모형으로 바꾸어 놓았다.[2] 이 작업은 이후 알고리즘과 계산 가능성에 대한 논의를 한층 명확하게 만들었다.
이후 튜링 기계는 여러 연구와 함께 계산 가능성 이론의 토대를 이루었고, 오늘날에는 디지털 컴퓨터의 이론적 기준점으로 받아들여진다.[3] 현대 컴퓨터 과학에서 이 모델이 갖는 위상은, 단순한 역사적 유물이라기보다 지금도 유효한 설명 언어라는 데 있다.[2][3]