검색어 입력폼

[공학]튜링기계 조사

저작시기 2007.01 |등록일 2007.06.29 한글파일한컴오피스 (hwp) | 8페이지 | 가격 2,000원

목차

Ⅰ. 튜링 기계(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 지식검색 -『고급언어와저급언어』검색결과물
다운로드 맨위로