[프로그래밍언어론] 4. 튜링 머신, 튜링 완전성

튜링 머신

• 1936년 앨런 튜링(Alan Turing)이 고안하였다.
• 원래는 자동 기계를 의미하는 "a-machine" 이라 불렀다.
• 계산 전반의 특성을 증명하기 위해 발명된 이론적이고 상상적인 기계
• 현대 컴퓨터의 기초

• 테이프(Tape) : 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록, 길이는 무한
• 헤드(Head) : 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드
• 행동표 : 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시
  기호 삭제나 수정, 헤드를 오른쪽/왼쪽 한 칸 이동, 상태를 변경
  
  
• 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 개수는 모두 유한해야 하며 서로 구분된다.
  
  1. '현재 상태가 1인데 기호 'A'를 읽었다면 'B'를 기록하고 정지.'
  2. '현재 상태가 1인데 기호 'B'를 읽었다면 오른쪽으로 한 칸 이동하고 상태 2로 변경'
  3. '현재 상태가 2인데 기호 'C'를 읽었다면 오른쪽으로 한 칸 이동'

튜링 완전성(Turing Completeness)

• 지금까지 모든 계산 문제는 튜링 머신으로 해결될 수 있는 것으로 알려져 있다.
  예) 컴퓨터로 할 수 있는 모든 일은 튜링 기계로도 할 수 있다.
• 튜링 머신을 시뮬레이션하는 데 사용할 수 있는 시스템은 튜링 완전(Turing Complete)
• 튜링 완전 시스템(Turing complete system)은 튜링 머신과 동등한 계산 능력을 가진다.
• 프로그래밍 언어의 이론적 계산 능력

어떤 컴퓨터 P가 있어서 그 컴퓨터와 보편 튜링 머신이 튜링 동치라면 P는 튜링 완전(Turing complete)하다.