E D R , A S I H C RSS

튜링 머신

last modified: 2015-02-19 02:10:53 by Contributors

본 항목은 튜링 기계로도 들어올 수 있습니다.


Contents

1. 개요
2. 개론
3. 컴퓨터와 튜링 머신
3.1. 튜링 동치(Turing Equivalence)
3.2. 튜링 완전성(Turing Completeness)
4. 튜링 완전한 언어
4.1. 절차적 언어
4.2. 다 대수(Lambda Calculus)
5. 참고 항목

1. 개요

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

...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings. (Turing 1948. p. 3)

...무한한 저장공간은 무한한 길이의 테이프로 나타나는데 이 테이프는 하나의 기호를 인쇄할 수 있는 크기의 정사각형들로 쪼개져있다. 언제든지 기계속에는 하나의 기호가 들어가있고 이를 "읽힌 기호"라고 한다. 이 기계는 "읽힌 기호"를 바꿀 수 있는데 그 기계의 행동은 오직 읽힌 기호만이 결정한다. 테이프는 앞뒤로 움직일 수 있어서 모든 기호들은 적어도 한번씩은 기계에게 읽힐 것이다. (한글번역. 출처 위키백과)

2. 개론

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

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

아래와 같은 개념을 일반화해 둔 것이다.

  • '현재 상태가 1인데 기호 'A'를 읽었다면 'B'를 기록하고 정지.'
  • '현재 상태가 1인데 기호 'B'를 읽었다면 오른쪽으로 한 칸 이동하고 상태 2로 변경'
  • '현재 상태가 2인데 기호 'C'를 읽었다면 오른쪽으로 한 칸 이동'

3. 컴퓨터와 튜링 머신

현대의 폰 노이만 구조로 된 컴퓨터는 모두 튜링 머신의 부분집합이다. 따라서 폰 노이만 구조의 컴퓨터로 할 수 있는 일은 모두 튜링 머신으로도 할 수 있다!!
하지만 약간의 차이점이 있는데 튜링 머신은 임의 접근을 상정하지 않고 있다. 테이프의 아무 위치나 원하면 바로 접근할 수는 없다. 이진 탐색 같은 알고리즘의 시간복잡도는 임의 접근이 가능하다면 O(lgN)시간 안에 끝나지만 튜링 머신에서는 훨씬 더 느린 속도를 보인다.

3.1. 튜링 동치(Turing Equivalence)

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

3.2. 튜링 완전성(Turing Completeness)

어떤 컴퓨터 P가 있어서 그 컴퓨터와 튜링 머신이 튜링 동치라면 P는 튜링 완전(Turing Complete)하다.
현대의 모든 컴퓨터는 튜링 완전하지 않은데, 그 이유는 기억장치가 유한하기 때문이다. '만일 기억장치가 무한하다면 이 컴퓨터는 튜링 완전하다'라고 생각할수도 있는데 이것을 '느슨한 튜링 완전성(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)

튜링 완전하다. 정확히는 람다 대수와 튜링 머신은 동치로 간주하자고 알론조 처치가 '제안'하였다. 람다 대수와 동치인 언어 역시 튜링 완전하다.

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2015-02-19 02:10:53
Processing time 0.0692 sec