기출14

Turing machine을 설명하시오?
==> 프로그램과 데이터를 기계에 주면 어떤 알고리즘도 실행 가능하다는 것을 추상적으로 증명한 기계.
Infinite linear tape와 R/W head와 아래와 같은 기본 동작을 가진 장치를 Turing machine 이라고 한다.
Turing machine=(si, dj, dk, R or L or N, sl)
D : tape의 문자 집합 {d1, d2, d3, ... ,dn}
S : state의 문자 집합 {s1, s2, s3, ... , sm}
si∈S : machine의 현 상태
dj∈D : R/W head가 위치한 곳의 문자
dk∈D : R/W head가 위치한 곳에 쓰여질 문자
R, L ,N : R/W head의 동작을 나타내느 문자, R은 head를 오른쪽으로, L은 head를 왼쪽으로, N은 현재위치로 정지 시킨다.
si∈S : 현 상태에서 모든 처리 동작을 자치고 종료될 상태