튜링 머신

최근 편집: 2017년 7월 31일 (월) 17:33

튜링 머신(Turing Machine)은 수학자 앨런 튜링이 고안한 가상의 계산 기계(또는 계산 모델)이다. 현재까지 알려진 계산 기계 중 가장 강력하다. 여기에서 말하는 강력함이란 계산가능성 측면에서의 강력함을 뜻한다. 다만 튜링 머신과 동등한(turing-equivalent) 여러 계산 방식이 무수히 존재한다는 점도 유념하자. 튜링 머신으로 풀 수 없는 문제는 현대 컴퓨터로도 풀 수 없다. 반면, 현대 컴퓨터는 무한대의 메모리가 제공되는 경우에 한하여 튜링 머신과 동등한 계산 능력을 갖게 된다. 물론 튜링 머신은 정의상 무한대의 기록 공간을 요구하기 때문에 엄밀한 의미에서는 현실에서 만들어낼 수 없다.