[include(틀:다른 뜻1, other1=인공지능을 판별하는 시험, rd1=튜링 테스트)]
[include(틀:수학기초론)]
[include(틀:컴퓨터공학)]
[include(틀:이론 컴퓨터 과학)]
[include(틀:앨런 튜링)]
[목차]

== 개요 ==
'''튜링 머신'''은 수학자 [[앨런 튜링]]이 [[1936년]]에 제시한 개념으로 [[컴퓨터|계산하는 기계]]의 일반적인 개념을 설명하기 위한 가상의 기계이며 [[오토마타]]의 일종이다. 튜링은 이 개념을 automatic에서 따온 a-machine이라고 불렀는데 튜링 사후에 창시자의 이름을 따 튜링 머신이라고 부르게 되었다.

== 구성 ==
튜링 머신은 아래와 같은 장치로 이루어진다:
 * 테이프(Tape): 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있다.
 * 헤드(Head): 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드. 이동이 가능하다. 또는 헤드는 고정되어 있고 테이프가 이동한다.
 * 상태 기록기(State register): 현재 튜링 머신의 상태를 기록하고 있는 장치.
  * 개시 상태(Start state): 상태 기록기가 초기화된 상태를 의미한다.
  * 종료 상태(Halt state): 수행이 종료된 상태.
 * 행동표(Action table, transition table of instructions): 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다.
  * 기호를 지우거나 고쳐 쓴다.
  * 헤드를 오른쪽, 왼쪽으로 한 칸 움직이거나 그 자리에 머문다.
  * 상태를 변경한다. 같은 상태에 머무를 수도 있다.

튜링 머신에서 종이 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 개수는 모두 유한해야 하며 서로 구분되어야 한다.

아래와 같은 개념을 일반화해 둔 것이다.
 * '현재 상태가 1인데 기호 'A'를 읽었다면 'B'를 기록하고 정지.'
 * '현재 상태가 1인데 기호 'B'를 읽었다면 오른쪽으로 한 칸 이동하고 상태 2로 변경'
 * '현재 상태가 2인데 기호 'C'를 읽었다면 오른쪽으로 한 칸 이동'

=== 보편 튜링 머신 ===
Universal Turing Machine.

원래의 튜링 머신은 행동표에 적힌 규칙에 따라서 할 수 있는 일이 정해져 있다. 그런데 우리는 모든 일을 다 처리할 수 있는 기계를 원하고 그래서 보편 튜링 머신이라는 개념이 나왔다. 보편 튜링 머신은 하나의 튜링 머신이지만 다른 임의의 튜링 머신을 시뮬레이션할 수 있다. 이것은 행동표에 해당하는 내용을 테이프에 적어놓음으로 가능하다. 상태집합 Q와 행동표 R로 이루어진 튜링 머신 M이 있다고 하면, 우선 Q와 R을 테이프에 기록해두고 이후 실제로 M이 수행할 작업을 테이프에 기록한다. 보편 튜링 머신은 먼저 Q와 R을 읽어서 내부적으로 상태 전이 [[그래프(이산수학)|그래프]]를 구축한다. 이후 테이프를 읽으며 실제로 M이 수행해야 할 작업을 수행한다. 이런 과정을 통해 모든 튜링 머신을 흉내낼 수 있는 보편 튜링 머신을 상정할 수 있다. 즉, 행동표와 작업 내용을 테이프(메모리) 하나에 모두 저장할 수 있다. 이것을 바탕으로 만든 계산기계가 [[폰 노이만 구조]] 컴퓨터로, 프로그램 내장형 컴퓨터 개념의 시초가 되었다.

최초의 보편 튜링 머신은 [[콘라드 추제]]의 Z3이었다. 그러나 최초의 디지털 연산 컴퓨터로는 [[콜로서스#s-3|콜로서스]]가 그 자리를 차지[* 원래 보편 튜링 머신이 아니지만, 10대를 모아 클러스터링 하면 보편 튜링 머신이 된다. - DOI 10.1007/s11047-010-9225-x ]한다.
=== 다중 테이프 튜링 머신 ===
Multitape Turing Machine.

헤드와 테이프가 여러개 달려 있는 튜링 머신. 기존의 튜링 머신에 비해 강력하고 폭넓은 작업을 해 줄 수 있으리라 예상하였으나, 헤드와 테이프를 몇 개 달아놓든 단일 테이프 튜링 머신과 동치라는 것이 증명되었다.

=== 튜링 동치(Turing equivalence) ===
만일 컴퓨터 P와 Q가 있을 때, P가 할 수 있는 일을 Q가 모두 흉내(simulate)낼 수 있고, Q가 할 수 있는 일을 모두 P가 흉내낼 수 있다면 두 컴퓨터는 튜링 동치이다.

=== 튜링 완전성(Turing completeness) ===
어떤 컴퓨터 P가 있어서 그 컴퓨터와 보편 튜링 머신이 튜링 동치라면 P는 튜링 완전(Turing complete)하다. 정확히 말하면 P가 보편 튜링 머신을 시뮬레이션 할 수 있으면 충분하다. 보편 튜링 머신은 모든 튜링 머신을 흉내낼 수 있다고 생각되므로 자동으로 동치가 된다.

== 컴퓨터와 튜링 머신 ==
현대의 [[폰 노이만 구조]]로 된 컴퓨터는 모두 보편 튜링 머신 이론에 바탕을 두고 있다. 따라서 보편 튜링 머신은 현대의 모든 컴퓨터의 동작을 포함하는 큰 집합이다. 코드 메모리와 데이터 메모리가 분리되어있는 하버드 구조는 테이프를 두 개 달아놓은 튜링 머신이라고 생각할 수 있으니 보편 튜링 머신은 하버드 구조의 컴퓨터도 완벽하게 흉내낼 수 있다. 이로 인하여 컴퓨터의 작업을 이론적으로 모델링할 때는 모두 튜링 머신 이론을 활용한다.

다만 현실의 컴퓨터와 튜링 머신에 약간의 차이점은 있는데, 튜링 머신은 메모리 임의 접근을 상정하지 않고 있다. 다시 말해 테이프의 아무 위치나 원하면 바로 접근할 수는 없다. [[이진 탐색]] 같은 알고리즘의 [[점근 표기법#s-3|시간복잡도]]는 임의 접근이 가능하다면 O(''lg''N) 시간 안에 끝나지만 튜링 머신에서는 훨씬 더 느린 O(N)의 속도를 보인다. 물론 이것은 접근 방식의 차이이지 튜링 머신도 유한한 행동 안에 그 접근을 똑같이 따라할 수 있으므로 기능적으론 동일하다.

현실의 모든 컴퓨터는 엄밀히 따지면 '튜링 완전'하지 않은데, 그 이유는 '''기억장치가 유한하기 때문'''이다. 튜링 머신의 테이프는 무한한 길이를 가져야 하는데 현실의 컴퓨터는 무한한 데이터를 보관할 수 없다. 다만 그렇다고 해서 컴퓨터들이 보편 튜링 머신을 무시한 것은 아니다. [[이상 기체]]는 현실에 없지만 이를 기반으로 한 [[이상 기체 법칙]]은 충분히 활용되는 것처럼 현실의 컴퓨터도 튜링 머신을 기반으로 설계되었기 때문에 유한한 작업을 수행함에 있어 그 이론을 충실히 따르고 있다. 

따라서 기억장치가 유한하지만 튜링 완전성을 따르고 있다는 것을 일컬어 '느슨한 튜링 완전성(Loose Turing Completeness)'이라고 한다. 대부분의 컴퓨터는 '느슨한 튜링 완전'이다. 그렇기 때문에 어떤 컴퓨터가 할 수 있는 모든 일은 [[니트로 박사|'충분한' 시간과 메모리만 주어진다면]] 다른 어떤 간단한 컴퓨터로도 할 수 있다. 여러분의 컴퓨터는 슈퍼컴퓨터와 다르지 않다. 다만 그보다 느리고 용량이 작을 뿐이다.

인터넷을 보면 [[마인크래프트]] [[레드스톤]]이나 [[롤러코스터 타이쿤]] 같은 게임으로 '컴퓨터'를 구현했다고 하는 글이나 영상을 종종 볼 수 있다. 이는 해당 게임들의 인게임 요소를 가지고 튜링 완전성을 따르는 장치를 구현한 것이다. 따라서 매우 비효율적이지만 컴퓨터와 마찬가지로 '느슨한 튜링 완전'이기 때문에 컴퓨터가 할 수 있는 일을 똑같이 할 수 있다. 마인크래프트로 계산기를 구현했다거나 하는 것들은 다 이런 뜻이다. 심지어 '''[[TCG]]'''인 [[매직 더 개더링]]으로 [[https://arxiv.org/abs/1904.09828|튜링 머신을 구현]]한 경우도 있다. 논문의 저자들은 60장의 적법한 [[레거시(매직 더 개더링)|레가시]] 포맷 덱으로 튜링 머신을 시뮬레이션하고 승리 조건을 [[정지 문제]]와 동치시킴으로서 최적의 플레이를 계산하는 알고리즘이 존재하지 않는다는 것을 증명했다.

== 튜링 완전한 언어 ==
어떤 언어의 튜링 완전성을 보이려면, 튜링 머신과 동치인, 이하 서술되는 다른 시스템과 동치임을 보이면 된다.
=== [[프로그래밍 언어/종류|절차적 언어]] ===
다음 두 가지 기능을 가지고 있다면 (느슨하게) 튜링 완전하다.
 1. 조건 분기문이 있다. if (...) then goto (...). 또는 branch if zero 등. for, while 등의 루프문은 모두 조건 분기문으로 바꿔 쓸 수 있다.
 1. 임의 위치의 메모리 값을 바꿀 수 있다.

[[C언어|C]], [[파스칼(프로그래밍 언어)|파스칼]] 등 널리 사용되는 절차적 언어는 대부분 위 두 조건을 충족하기에 튜링 완전하다. [[난해한 프로그래밍 언어]]에서 소개되는 대부분의 절차적 언어 역시 위 두 조건을 충족하기에 튜링 완전하다. C++의 템플릿 메타 프로그래밍도 컴파일 타임 튜링 완전하다.

''''[[HTML]]은 프로그래밍 언어가 아니다\''''라는 말은 여기서 나온 것이다. HTML은 조건 분기도 없으며 메모리를 바꾸는 것도 불가능하기 때문에 튜링 완전하지 않기 때문이다. [[프로그래밍 언어/종류]] 문서를 보면 알겠지만 이런 언어들은 '[[마크업 언어]]'라고 해서 따로 분류한다. 다만 HTML5와 CSS3의 조합은 튜링 완전하다고 증명된 110 세포자동자를 흉내낼 수 있으므로 튜링완전하다.

실용적인 사례는 아니지만 좀 극단적인 예 하나는 단일 인스트럭션 컴퓨터(One Instruction Set Computer)이다. [[http://en.wikipedia.org/wiki/One_instruction_set_computer|영문 위키백과의 항목]]을 보면 '빼기 연산을 하고 결과가 0 이하이면 점프(SUbtract and Branch if Less than or EQual to zero = SUBLEQ)'하는 연산 하나만으로 임의 위치의 메모리 값 바꾸기, 조건 분기하기를 구현하고 있다. 이 경우 역시 위 두 조건을 만족하니 튜링 완전하다.

=== 람다 대수(Lambda calculus) ===
람다 대수는 알론조 처치에 의해 튜링 기계보다 먼저 제안된 계산 모델이며 람다 대수로 할 수 있는 모든 계산은 튜링 기계로도 가능하고 그 역도 성립한다는 것이 증명되었다. 람다 대수와 동치인 언어 역시 튜링 완전하다. 프로그래밍 언어에서는 튜링 기계보다 람다 대수를 더 널리 이용한다.

== 튜링 머신의 한계 ==
튜링 머신은 우리가 상상할 수 있는 거의 모든 계산을 할 수 있다. 다만 모든 것을 할 수 있지는 않다. 예를 들어 어떤 튜링 머신이 주어진 입력에 대해 유한 시간 내에 정지하는지를 묻는 문제는 튜링 머신으로 답할 수 없다. 이것이 [[정지 문제]]이다.

이것을 비롯하여 수많은 문제들이 튜링 머신으로 할 수 없음이 증명되었다. 대부분의 증명 방식은 문제를 정지 문제와 동치인 문제로 변형하는 형식이다.
== 처치-튜링 명제 ==
Church-Turing thesis.
[[알고리즘]]으로 할 수 있는 모든 일이 튜링 기계로 실행될 수 있다는 것이다. 현재까지 알려진 모든 알고리즘들은 튜링 기계로 실행될 수 있다고 추측된다. 그러나 알고리즘의 정의가 명확하지 않으므로 이 명제가 증명되기는 어렵다. [[양자컴퓨터]] 또한 이것을 벗어나지 않는다. 지금까지 알려진 모든 양자컴퓨터는 튜링 기계에 의해 시뮬레이션될 수 있고 역시나 처치-튜링 명제가 성립한다. 대부분의 학자들은 처치-튜링 명제가 참일 것이라고 여기고 있다. 다시 말하자면 위에서 말한 튜링 머신의 한계들은 어떤 방법으로도 해결 불가능할 것이라고 생각되고 있다.

처치-튜링 명제는 사람의 뇌 또한 하나의 컴퓨터에 지나지 않을 수 있음을 암시하고 있다. 그런데 오히려 [[로저 펜로즈]] 등은 인간의 뇌가 컴퓨터와 다른 능력을 지녔으며 그렇기 때문에 처치-튜링 명제가 완전하지 않다고 여긴다. 펜로즈는 [[불완전성 정리]]에 의해 튜링 기계, 다시 말해 모든 기계적 컴퓨터에는 한계가 존재하는데 사람의 뇌는 그렇지 않다는 것이다. 그렇기 때문에 알려지지 않은 어떤 새로운 [[양자역학]]의 개선에 의해 튜링 기계보다 뛰어난 능력을 가질 수 있다는 것이다. 그러나 철학적으로 문제가 많은 주장이기에 주류 학계에서는 진지하게 받아들여지지 않는다.

한국에는 잘 알려지지 않았지만 더 강한 버전으로 Church–Turing–Deutsch principle이란 것이 존재한다. 알고리즘을 넘어서 아예 모든 물리적 과정이 튜링 기계로 시뮬레이션될 수 있다는 것이다. 다만 이 때는 시뮬레이션의 정의도 명확치 않을뿐더러 처치-튜링 명제와 마찬가지로 증명되기는 어려운 성질의 것이다.

[[1936년]] [[수리논리학]]자인 알론조 처치가 먼저 제안했기 때문에 처치의 명제를 따로 구분하여 부르기도 한다. 처치의 명제는 결정가능한 모든 계산가능한 함수가 재귀적이라는 것이다. 같은 해인 1936년에 [[앨런 튜링]]이 튜링 머신을 통해 별개의 방향으로 이를 이상화시켜 나타난 개념이 처치-튜링 명제이다.

== 관련 문서 ==
 * [[앨런 튜링]]
 * [[오토마타]]
 * [[폰 노이만 구조]]
 * [[앨런 처치]]
 * [[알고리즘]]
 * [[프로그래밍 언어]]
 * [[해석기관]] - 튜링 머신의 개념이 등장하기 전에 구상된 기계식 연산장치로, 튜링 머신의 조건을 만족하여 컴퓨터의 역할을 수행할 수 있다.
 * [[정지 문제]]
 * [[바쁜 비버]]
 * [[컴퓨터 관련 정보]]
 
[[분류:이론전산학]][[분류:수학]][[분류:컴퓨터 공학]][[분류:앨런 튜링]]