[공학]튜링기계 조사

목차

Ⅰ. 튜링 기계(Turing machine)
1. 튜링 기계의 정의
2. 언어 인식기로서의 튜링 기계
3. 계산이 가능한 언어들과 함수들
4. 변형된 튜링머신들
4.1 다중테이프(multi-tape)튜링머신
4.2 비결정적 튜링머신 6
4.3 다차원(Multi-dimensional)튜링 머신
4.4 다중헤드(Multi-head)튜링 머신

Ⅱ. 기계가 쉽게 판독한다는 의미

Ⅲ. 인간이 쉽게 판독한다는 의미

Ⅳ. 참고문헌

본문내용

Ⅰ. 튜링 기계(Turing machine)
우리는 복잡하고 정교한 저장장소를 갖는 다양한 오토마타를 상상할 수 있지만, 튜링 기계의 저장장소는 실제로 아주 간단하다. 그 저장장소는 셀(cell)들의 1차원 배열로 구체화할 수 있다. 각 셀은 하나의 심볼을 저장할 수 있다. 이 배열은 양쪽으로 무한히 확장되고 따라서 무한한 양의 정보를 저장할 수 있다. 그 정보는 어떤 순서로도 읽혀질 수 있고 바뀔 수도 있다. 우리는 그런 저장장소를, 실제 컴퓨터에서 사용되는 자성 테이프와 유사하기 때문에, 테이프 (tape) 라 한다.

1. 튜링 기계의 정의
튜링 기계는 영국의 수학자인 앨런 튜링(Alan Turing)에 의해 고안된 가상(假想)의 자동기계로서 테이프를 일시 기억 장치로 갖는 오토마타이다. 이 테이프는 기억 소자들로 나누어져 있으며, 이 기억 소자는 한 개의 기호를 저장할 수 있다. 테이프에는 테이프 입출력 헤드(read-write head)가 존재하며 테이프의 좌우 방향으로 이동하면서 각 작동(move)마다 하나의 기호를 읽거나 쓴다.
오토마타와 다른 점은 특별한 입력 장치나 출력 기능이 없다는 점이다. 필요한 입출력은 모두 테이프에 의해 이루어진다. [그림 Ⅰ-1]은 튜링 기계의 구성을 보여주며, 튜링 기계의 정의는[정의 Ⅰ-1]과 같다.











테이프
입출력 헤드
컨트롤
유니트

[그림 Ⅰ-1] 튜링 기계

[ 정의 Ⅰ-1 ]
튜링기계 M은

M = (Q, Σ, Γ, δ, q0, B, F)

로 정의되며, 여기서 각 기호는 다음을 의미한다.

∙ Q : set of state symbols (내부 상태의 유한 집합)
∙ Σ : input alphabet (입력 알파벳의 유한 집합이며, B를 포함하지 않는 T의 부분집합,
∑ ⊆ T - {B} )
∙ T : tape alphabet (기호들의 유한 집합인 테이프 알파벳)
∙ δ : mapping(전이함수), Q × T → Q × T × {L,R}
∙ q0∈Q : initial state (초기상태)
∙ B∈Γ : (blank symbol) 공백을 표시하는 기호
∙ F⊆Q : the set of final states (최종 상태들의 집합)

참고자료

· 1. Peter Linz저서, 장직현․김응모․엄영익․한광록 공역, “형식 언어와 오토마타”, 사이텍미디어
· 2. 김대수, “오토마타와 계산이론”, 생능출판사
· 3. 유은진․방혜자․전문석 공저, “형식언어와 오토마타론”, 홍릉과학출판사
· 4. NAVER 지식검색 -『고급언어와저급언어』검색결과물