튜링 머신 (Turing Machine)

튜링 머신(Turing Machine)은 앨런 튜링이 1936년에 제안한 계산의 이론적 모형으로, 무한히 긴 테이프와 그 위를 읽고 쓰는 헤드, 유한한 규칙 집합만으로 계산을 기술하는 추상적인 기계입니다. 명확한 절차로 기술할 수 있는 계산(알고리즘)은 튜링 머신으로 표현할 수 있다고 여겨지며(처치-튜링 논제), 이 때문에 컴퓨터가 원리적으로 무엇을 계산할 수 있는지 이해하는 기본 개념으로 쓰입니다.

구성 요소

• 칸(셀)으로 나뉜 무한히 긴 테이프. 각 칸에는 유한한 알파벳의 기호 하나가 적힙니다.
• 테이프의 한 칸을 읽고, 기호를 쓰고, 왼쪽이나 오른쪽으로 한 칸 이동하는 헤드.
• 현재 상태와 헤드가 읽은 기호에 따라 쓸 기호, 이동 방향, 다음 상태를 정하는 유한한 규칙 표(전이 함수). 정지 상태에 이르면 계산이 끝납니다.

튜링 머신과 범용 튜링 머신

개별 튜링 머신은 하나의 고정된 알고리즘만 실행합니다. 이에 비해 범용 튜링 머신은 다른 튜링 머신의 규칙 표를 테이프에 입력으로 받아 그 동작을 그대로 흉내 낼 수 있는 튜링 머신입니다. “어떤 알고리즘이든 시뮬레이션할 수 있다”는 설명은 엄밀히 말하면 범용 튜링 머신에 해당하며, 프로그램을 데이터로 읽어 실행하는 오늘날 컴퓨터의 이론적 원형입니다. 요리사에 비유하면 한 가지 요리만 만드는 요리사가 개별 튜링 머신이고, 어떤 레시피든 받아서 따라 할 수 있는 요리사가 범용 튜링 머신입니다.

계산의 한계

튜링 머신은 계산할 수 없는 문제도 있다는 것을 보여 줍니다. 대표적인 예가 정지 문제로, 임의의 프로그램이 언젠가 멈출지 아니면 영원히 실행될지를 판정하는 일반적인 알고리즘은 존재하지 않는다는 것이 튜링 머신으로 증명되었습니다. 또한 튜링 머신은 이론적 구성물이므로 실제 계산에 쓰기에는 매우 느리고 비실용적입니다.

튜링 완전성과 블록체인

어떤 시스템이 범용 튜링 머신과 같은 계산을 표현할 수 있으면 튜링 완전하다고 합니다. 이더리움 가상 머신(EVM)은 반복과 조건 분기를 지원하는 튜링 완전한 실행 환경으로 설계되어 임의의 스마트 계약 로직을 실행할 수 있습니다. 다만 정지 문제 때문에 계약이 끝날지 미리 알 수 없으므로, 이더리움은 연산마다 가스를 부과하고 가스 한도를 두어 실행을 반드시 끝나게 합니다. 반면 비트코인 스크립트는 반복문이 없는 의도적으로 제한된 언어입니다.

응용 분야

• 이론 컴퓨터 과학: 계산 가능성을 정의하고 알고리즘의 한계를 탐구합니다.
• 계산 복잡도 이론: 알고리즘에 필요한 단계 수와 메모리를 분석하는 기준 모형으로 쓰입니다.
• 프로그래밍 언어와 실행 환경 설계: 언어나 가상 머신이 튜링 완전한지, 그에 따른 위험을 어떻게 제한할지 판단하는 기준이 됩니다.