목차
1 개요
수학자 앨런 튜링이 1936년에 제시한 개념으로 계산하는 기계의 일반적인 개념을 설명하기 위한 가상의 기계이며 오토마타의 일종이다. 튜링은 이 개념을 automatic에서 따온 a-machine이라고 불렀는데 튜링 사후에 창시자의 이름을 따 튜링 머신이라고 부르게 되었다.
2 개론
튜링 머신은 아래와 같은 장치로 이루어진다:
- 테이프(Tape) : 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있다.
- 헤드(Head) : 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드. 이동이 가능하다. 또는 헤드는 고정되어 있고 테이프가 이동한다.
- 상태 기록기(State register) : 현재 튜링 머신의 상태를 기록하고 있는 장치.
- 개시 상태(Start state) : 상태 기록기가 초기화된 상태를 의미한다.
- 종료 상태(Halt state) : 수행이 종료된 상태.
- 행동표(Action table, transition table of instructions) : 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다.
- 기호를 지우거나 고쳐 쓴다.
- 헤드를 오른쪽, 왼쪽으로 한 칸 움직이거나 그 자리에 머문다.
- 상태를 변경한다. 같은 상태에 머무를 수도 있다.
튜링 머신에서 종이 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 개수는 모두 유한해야 하며 서로 구분되어야 한다.
아래와 같은 개념을 일반화해 둔 것이다.
- '현재 상태가 1인데 기호 'A'를 읽었다면 'B'를 기록하고 정지.'
- '현재 상태가 1인데 기호 'B'를 읽었다면 오른쪽으로 한 칸 이동하고 상태 2로 변경'
- '현재 상태가 2인데 기호 'C'를 읽었다면 오른쪽으로 한 칸 이동'
2.1 보편 튜링 머신
Universal Turing Machine.
원래의 튜링 머신은 행동표에 적힌 규칙에 따라서 할 수 있는 일이 정해져 있다. 그런데 우리는 모든 일을 다 처리할 수 있는 기계를 원하고 그래서 보편 튜링 머신이라는 개념이 나왔다. 보편 튜링 머신은 하나의 튜링 머신이지만 다른 임의의 튜링 머신을 시뮬레이션할 수 있다. 이것은 행동표에 해당하는 내용을 테이프에 적어놓음으로 가능하다. 상태집합 Q와 행동표 R로 이루어진 튜링 머신 M이 있다고 하면, 우선 Q와 R을 테이프에 기록해두고 이후 실제로 M이 수행할 작업을 테이프에 기록한다. 보편 튜링 머신은 먼저 Q와 R을 읽어서 내부적으로 상태 전이 그래프를 구축한다. 이후 테이프를 읽으며 실제로 M이 수행해야 할 작업을 수행한다. 이런 과정을 통해 모든 튜링 머신을 흉내낼 수 있는 보편 튜링 머신을 상정할 수 있다. 즉, 행동표와 작업 내용을 테이프(메모리) 하나에 모두 저장할 수 있다. 이것을 바탕으로 만든 계산기계가 폰 노이만 구조 컴퓨터로, 프로그램 내장형 컴퓨터 개념의 시초가 되었다.
2.2 다중 테이프 튜링 머신
Multitape Turing Machine.
헤드와 테이프가 여러개 달려 있는 튜링 머신. 기존의 튜링 머신에 비해 강력하고 폭넓은 작업을 해 줄 수 있으리라 예상하였으나, 헤드와 테이프를 몇 개 달아놓든 단일 테이프 튜링 머신과 동치라는 것이 증명되었다.
2.3 튜링 동치(Turing Equivalence)
만일 컴퓨터 P와 Q가 있을 때, P가 할 수 있는 일을 Q가 모두 흉내(Simulate)낼 수 있고, Q가 할 수 있는 일을 모두 P가 흉내낼 수 있다면 두 컴퓨터는 튜링 동치이다.
2.4 튜링 완전성(Turing Completeness)
어떤 컴퓨터 P가 있어서 그 컴퓨터와 보편 튜링 머신이 튜링 동치라면 P는 튜링 완전(Turing Complete)하다. 정확히 말하면 P가 보편 튜링 머신을 시뮬레이션 할 수 있으면 충분하다. 보편 튜링 머신은 모든 컴퓨터를 흉내낼 수 있다고 생각되므로 자동으로 동치가 된다.
3 컴퓨터와 튜링 머신
현대의 폰 노이만 구조로 된 컴퓨터는 모두 보편 튜링 머신 이론에 바탕을 두고 있다. 따라서 보편 튜링 머신은 현대의 모든 컴퓨터를 흉내낼 수 있다. 코드 메모리와 데이터 메모리가 분리되어있는 하버드 구조는 테이프를 두 개 달아놓은 튜링 머신이라고 생각할 수 있으니 보편 튜링 머신은 하버드 구조의 컴퓨터도 완벽하게 흉내낼 수 있다. 이로 인하여 컴퓨터의 작업을 이론적으로 모델링할 때 튜링 머신을 활용한다.
하지만 약간의 차이점이 있는데 튜링 머신은 임의 접근을 상정하지 않고 있다. 테이프의 아무 위치나 원하면 바로 접근할 수는 없다. 이진 탐색 같은 알고리즘의 시간복잡도는 임의 접근이 가능하다면 O(lgN) 시간 안에 끝나지만 튜링 머신에서는 훨씬 더 느린 속도를 보인다.
현대의 모든 컴퓨터는 튜링 완전하지 않은데, 그 이유는 기억장치가 유한하기 때문이다. '만일 기억장치가 무한하다면 이 컴퓨터는 튜링 완전하다'라고 생각할수도 있는데 이것을 '느슨한 튜링 완전성(Loose Turing Completeness)'이라고 한다. 대부분의 컴퓨터는 느슨하게 튜링 완전하다. 그렇기 때문에 어떤 컴퓨터가 할 수 있는 모든 일은 충분한 시간과 메모리만 주어진다면 다른 어떤 간단한 컴퓨터로도 할 수 있다. 여러분의 컴퓨터는 나사의 슈퍼컴퓨터와 다르지 않다. 다만 조금이라하기에는 조금 많이 느릴 뿐이다.
4 튜링 완전한 언어
어떤 언어의 튜링 완전성을 보이려면, 튜링 머신과 동치인 다른 시스템과 동치임을 보이면 된다.
4.1 절차적 언어
다음 두 가지 기능을 가지고 있다면 (느슨하게) 튜링 완전하다.
1. 조건 분기문이 있다. if (...) then goto (...). 또는 branch if zero 등. for, while 등의 루프문은 모두 조건 분기문으로 바꿔 쓸 수 있다.
2. 메모리의 임의 위치의 값을 바꿀 수 있다.
C, 파스칼 등 널리 사용되는 절차적 언어는 대부분 위 두 조건을 충족하기에 튜링 완전하다. 난해한 프로그래밍 언어에서 소개되는 대부분의 절차적 언어 역시 위 두 조건을 충족하기에 튜링 완전하다.
실용적인 사례는 아니지만 좀 극단적인 예 하나는 단일 인스트럭션 컴퓨터(One Instruction Set Computer)이다. 영문 위키백과의 항목을 보면 '빼기 연산을 하고 결과가 0 이하이면 점프(SUbtract and Branch if Less than or EQual to zero = SUBLEQ)'하는 연산 하나만으로 임의 위치의 메모리 값 바꾸기, 조건 분기하기를 구현하고 있다. 이 경우 역시 위 두 조건을 만족하니 튜링 완전하다.
4.2 람다 대수(Lambda Calculus)
람다 대수는 알론조 처치에 의해 튜링 기계보다 먼저 제안된 계산 모델이며 람다 대수로 할 수 있는 모든 계산은 튜링 기계로도 가능하고 그 역도 성립한다는 것이 증명되었다. 람다 대수와 동치인 언어 역시 튜링 완전하다. 프로그래밍 언어에서는 튜링 기계보다 람다 대수를 더 널리 이용한다.
5 튜링 머신의 한계
튜링 머신은 우리가 상상할 수 있는 거의 모든 계산을 할 수 있다. 다만 모든 것을 할 수 있지는 않다. 예를 들어 어떤 튜링 머신이 정지할까를 묻는 문제는 튜링 머신으로 답할 수 없다. 이것이 정지 문제이다. 이것을 비롯하여 수많은 문제들이 튜링 머신으로 할 수 없음이 증명되었다. 이 증명들은 대부분 문제를 정지 문제와 동치인 문제로 변형하여 증명한다. 정지 문제는 본질적으로 불완전성 정리와 동치이다. 튜링은 불완전성 정리를 응용하여 정지 문제를 증명해냈으며 정지 문제를 이용하여 불완전성 정리를 증명할 수 있다.
6 처치-튜링 명제
Church-Turing thesis.
모든 알고리즘으로 할 수 있는 모든 일이 튜링 기계로 실행될 수 있다는 것이다. 현재의 컴퓨터를 비롯하여 알려진 모든 알고리즘들은 튜링 기계로 실행될 수 있다고 추측된다. 그러나 알고리즘의 정의가 명확하지 않으므로 이 명제가 증명되기는 어렵다. 양자컴퓨터 또한 이것을 벗어나지 않는다. 지금까지 알려진 모든 양자컴퓨터는 튜링 기계에 의해 시뮬레이션될 수 있고 역시나 처치-튜링 명제가 성립한다. 대부분의 학자들은 처치-튜링 명제가 참일 것이라고 여기고 있다. 그리고 다시 말해서 위에서 말한 튜링 머신의 한계들은 어떤 방법으로도 불가능할 것이다.
처치-튜링 명제는 사람의 뇌 또한 하나의 컴퓨터에 지나지 않을 수 있음을 암시하고 있다. 그런데 오히려 로저 펜로즈 등은 인간의 뇌가 컴퓨터와 다른 능력을 지녔으며 그렇기 때문에 처치-튜링 명제가 완전하지 않다고 여긴다. 펜로즈는 불완전성 정리에 의해 튜링 기계, 다시 말해 모든 기계적 컴퓨터에는 한계가 존재하는데 사람의 뇌는 그렇지 않다는 것이다. 그렇기 때문에 알려지지 않은 어떤 새로운 양자역학의 개선에 의해 튜링 기계보다 뛰어난 능력을 가질 수 있다는 것이다. 그러나 철학적으로 문제가 많은 주장이기에 주류 학계에서는 진지하게 받아들여지지 않는다.
한국에는 잘 알려지지 않았지만 더 강한 버전으로 Church–Turing–Deutsch principle이란 것이 존재한다. 알고리즘을 넘어서 아예 모든 물리적 과정이 튜링 기계로 시뮬레이션될 수 있다는 것이다. 다만 이 때는 시뮬레이션의 정의도 명확치 않을뿐더러 처치-튜링 명제와 마찬가지로 증명되기는 어려운 성질의 것이다.
1936년 수리논리학자인 알론조 처치가 먼저 제안했기 때문에 처치의 명제라 부르기도 한다. 처치의 명제는 결정가능한 모든 계산가능한 함수가 재귀적 이라는 것이다. 같은 해인 1936년에 앨런 튜링이 튜링 머신을 통해 별개의 방향으로 이를 이상화시켜 나타난 개념이 처치-튜링 명제이다.