Turing Machine   튜링 기계, 튜링 머신

1. 계산 기계 (Computational Machine) 이란?

  ㅇ 컴퓨터에 대한 수학적/추상적 모델화에 따른, 호칭
     - 즉, `계산할 수 있는 것`에 대한 수학적 정의
     - 결국, `계산이란 무엇인가?`라는 질문에,
        . 답을 제시할 수 있는, 수학적 기초를 마련하고, 
        . 이를 구현하는 방법을 찾으려고 하는 것임

  ※ 1930년대에, 쿠르트 괴델(Kurt Gödel), 알론조 처치(Alonzo Church), 에밀 포스트(Emil Post),
     앨런 튜링(Alan Turing) 등에 의해 연구됨


2. 튜링 머신 (Turing Machine) 이란?

  ㅇ 프로그램화될 수 있는 계산 기계
     - 기억 영역을 갖고 분명한 답이 있는 계산을 할 수 있는 것

  ㅇ 컴퓨터의 이론적 모델
     - 계산 기계에 대한 가상적인 모형

  ㅇ 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸어, 
     기계적 계산 원리를 설명

  ㅇ `계산가능함 (computability)`를 정의하는데 도움을 줌

  ※ 튜링 (Alan Turing, 1912-54) : 영국의 컴퓨터 과학자이자 수학자


3. 튜링 머신의 구성 요소 다섯(5)

  ㅇ 테이프 : 무한 길이 (입력,저장장치)
     - 기계가 인식하거나 기록할 수 있는 기호들이 저장됨
     - 연산을 위해, 무한한 저장 공간을 가진 기계
  ㅇ 기호 : 유한 종류 (알파벳 집합)
  ㅇ 헤드 : 테이프를 이동하며, 기호를 읽고 쓸 수 있음 (CPU)
     - 그 동작은 현재 상태와 읽은 기호에 따라 정해짐
        . 같은 상태라도 읽은 기호에 따라 동작이 달라짐
  ㅇ 상태 : 유한 종류 (유한 상태 집합)
  ㅇ 규칙 : 상태,기호에 따른 헤드 동작을 정해 둔 것 (알고리즘)

  ※ 기호,상태,동작은, 모두 유한 이며, 이산적 이며, 구분 가능 함

  ※ 결국, 주어지는 테이프와 규칙에 따라 동작하는 기계 (추상적인 계산 기계 모형)


4. 튜링 머신의 종류

  ㅇ 결정론적/비결정론적
     - 결정론적 튜링 기계
        . 오직 한가지 상태로 만 바뀔 수 있음 (순차 처리)
     - 비결정론적 튜링 기계
        . 1 이상의 상태로 바뀔 수 있거나, 바뀔 상태 없음 (병렬 처리)

  ㅇ 만능 튜링 머신