튜링 완전(turing-complete)이란?

튜링 완전이란?

튜링 완전(turing complete)이란 어떤 프로그래밍 언어나 추상 머신이 튜링 머신과 동일한 계산 능력을 가진다는 의미이며 튜링 머신으로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 머신으로 풀 수 있다는 의미입니다.

튜링이란?

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

라고 나무위키에서 정의되어 있습니다.

튜링 머신 장치

테이프(Tape) : 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있음

헤드(Head) : 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드. 이동이 가능하다. 또는 헤드는 고정되어 있고 테이프가 이동

상태 기록기(State register) : 현재 튜링 머신의 상태를 기록하고 있는 장치

• 개시 상태(Start state) : 상태 기록기가 초기화된 상태를 의미

• 종료 상태(Halt state) : 수행이 종료된 상태

행동표(Action table, transition table of instructions) : 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시

• 기호를 지우거나 고쳐 씀

• 헤드를 오른쪽, 왼쪽으로 한 칸 움직이거나 그 자리에 머뭄

• 상태를 변경한다. 같은 상태에 머무를 수도 있음

튜링머신에 대해 복잡한 문서가 있는데 컴퓨터는 보편 튜링 머신 이론에 바탕을 두고 있습니다. 간단하게 컴퓨터 = 튜링머신 이라고 이해하는게 빠릅니다(약간의 차이가 존재). 따라서 튜링 머신은 컴퓨터를 흉내낼 수 있습니다. 컴퓨터의 작업을 이론적으로 모델링할 때 튜링 머신을 활용합니다.

물론 약간의 차이점이 있는데 튜링 머신은 아무 위치나 원할 때 접근할 수 없습니다. 이진탐색(binary search)와  같은 알고리즘의 시간복잡도는 임의 접근이 가능하다면 O(logN) 시간이 걸리지만 튜링 머신에서는 O(N)의 시간이 걸립니다.

현실의 모든 컴퓨터 또한 튜링 완전하지 않은데, 그 이유는 기억장치가 유한하기 때문입니다. '만일 기억장치가 무한하다면 이 컴퓨터는 튜링 완전하다'라고 생각할 수도 있는데 이것을 느슨한 튜링 완전성(Loose Turing Completeness)이라고 합니다. 대부분의 컴퓨터는 느슨하게 튜링 완전합니다. 그렇기 때문에 어떤 컴퓨터가 할 수 있는 모든 일은 아주 충분한 시간과 메모리만 주어진다면 다른 어떤 간단한 컴퓨터로도 할 수 있습니다.

요약

• 튜링은 계산하는 기계를 만든 사람의 이름을 따옴
• 튜링완전하다는 것은 튜링머신과 동일한 계산능력을 지녔다는 의미
• 복잡하게 더 이해할 필요성을 못느낌