Turing Machine   튜링 기계, 튜링 머신

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

  ㅇ 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계
  ㅇ 컴퓨터의 이론적 모델
     - 계산 기계에 대한 가상적인 모형
  ㅇ `계산가능함 (computability)`를 정의하는데 도움을 줌


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

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

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

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


3. 튜링 머신의 종류

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

  ㅇ 만능 튜링 머신
  ㅇ (추가편집중)