튜링 기계 (Turing Machine)
쉽게 풀면
칸이 무한히 이어진 테이프와, 그 위를 한 칸씩 오가며 기호를 읽고 지우고 새로 쓸 수 있는 헤드 하나만 있다고 상상해보세요. 이 헤드는 "지금 어떤 상태이고 어떤 기호를 읽었는지"에 따라 "무엇을 쓰고, 어느 방향으로 움직이고, 어떤 상태로 바뀔지"를 정해진 규칙표대로만 따릅니다. 놀랍게도 앨런 튜링은 이렇게 극도로 단순한 기계만으로도 우리가 "계산"이라고 부를 수 있는 모든 것을 원리적으로 수행할 수 있음을 보였습니다. 그래서 튜링 기계는 스마트폰이든 슈퍼컴퓨터든 "이론적으로 계산할 수 있는 것"의 한계를 정의하는 기준선 역할을 합니다.
왜 중요한가
튜링 기계는 "계산 가능하다"는 말의 뜻 자체를 정의하는 기준점이기 때문에, 계산이론과 알고리즘 복잡도 연구 전반의 출발점 역할을 합니다. 어떤 문제가 풀릴 수 있는지 없는지(결정 가능성), 얼마나 효율적으로 풀 수 있는지(복잡도 이론)를 논하려면 먼저 "무엇을 계산이라고 부를 것인가"에 대한 공통 기준이 필요한데, 튜링 기계가 바로 그 역할을 합니다. 그래서 새로운 계산 모델이나 프로그래밍 언어의 표현력을 논할 때도 흔히 튜링 기계와 비교하는 방식으로 설명이 이루어집니다.
논문에서는 이렇게 쓰입니다
이 문장은 어떤 문제를 튜링 기계가 풀 수 있는 형태로 바꿔볼 수 있다는 것을 보여, 그 문제가 원리적으로 알고리즘으로는 항상 풀 수 없는 문제(결정 불가능한 문제)임을 논리적으로 증명했다는 뜻입니다.
복잡도 이론 연구에서 문제의 난이도를 비교할 때도 튜링 기계를 기준으로 한 환원 논증이 쓰인다는 것을 보여주는 예문이다.
인공지능이나 계산 모델 연구에서도 새로운 시스템의 표현력 한계를 논할 때 튜링 기계가 비교 기준으로 사용된다는 것을 보여준다.
조금 더 깊게 보면
튜링 기계에는 결정론적 튜링 기계 외에도, 각 단계에서 여러 선택지를 동시에 탐색한다고 가정하는 비결정론적 튜링 기계 같은 변형이 있으며, 이는 P와 NP 같은 복잡도 클래스를 정의하는 데 쓰입니다. 또한 튜링 기계와 계산 능력이 동등하다고 증명된 다른 모델들(람다 계산법, 재귀함수 등)이 여러 개 존재한다는 사실은 처치-튜링 명제(Church-Turing thesis)로 알려져 있으며, 이는 "계산 가능성"에 대한 서로 다른 정의들이 결국 같은 능력으로 수렴한다는 것을 시사합니다. 논문에서 "다항 시간 환원"이나 "계산 가능성" 같은 표현을 볼 때, 그 배경에는 이런 튜링 기계 기반의 정의가 깔려 있다고 이해하면 도움이 됩니다.
주의할 점
튜링 기계는 실제로 만들어 쓰는 하드웨어가 아니라 "계산이란 무엇인가"를 정의하기 위한 수학적 개념입니다. 튜링 기계로 원리상 풀 수 있다고 해서 실제로 빠르게 풀 수 있다는 뜻은 아니며, 그 문제의 실행 속도나 자원 소모는 시간복잡도와 빅오 표기법이나 NP-완전성 같은 별도의 잣대로 따로 따져야 합니다.