튜링머신

목차

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

2.튜링머신의 영향

3.튜링머신의 구조

4.튜링머신의 정의

5.튜링머신의 기능
5. 1 Halting(중단)
5. 2 Termination(종료)
5. 3 Ambiguous(모호성)
5. 4 수의 표현과 이용
5. 5 문자의 탐색

6.튜링머신의 7가지 요소

7.참고 문헌 / 사이트 주소

본문내용

다. 이러한 동작을 하는 튜링머신의 매핑 테이블은 임의의 입력자료에 대하여 다음과 같이 작성한다. 매핑 테이블에서 "-" 기호는 특수문자 #와 *을 제외한 모든 문자를 의미한다.
6. 튜링머신의 7가지 요소
○ M = (Q, Σ, Γ, δ, q0, B, F)
○ Q : 상태들의 유한 집합
○ Σ : 입력 알파벳의 유한 집합이며, B를 포함하지 않는 Γ의 부분집합
○ Γ : 테이프 알파벳의 유한 집합
○ δ : 동작함수, Q×Γ→Q×Γ×{L,R}
○ q0∈Q : 초기상태
○ B∈Γ : 블랭크 표시
○ F⊆Q : 최종상태들의 집합
<동 작>
전이함수 : δ(q0, a) → (q1, b, R)
δ(현재상태, 입력) → (새로운상태, 출력(입력에 덮어씀), 헤드의 이동 방향)
순간묘사(Instantaneous Description : ID) : 특정한 순간의 튜링머신의 상황을 표시
α1 q α2 로 표시
여기서, q는 상태를, α1과은 헤드왼쪽의 스트링, α2는 헤드오른쪽의 스트링이다.
○ <동작의 멈춤>
1. 최종상태에 도착한 경우
2. 전이함수가 정의되지 않은 경우
○ 언어 인식기로서의 튜링머신
최종상태에 도착하면 동작을 정지하고 인식
○ 계산이 가능한 언어들과 함수들 :
순환적 열거 가능 언어(recursively enumerable language) : 그 언어를 인식하는 튜링머신이 언어에 속하지 않는 스트링에 대해서는 멈추지 않는다.
7. 참고 문헌 / 사이트 주소
● 참고 문헌
○ 김대수, 오토마타와 계산이론, 생능출판사, 1998.
○ 김대수, 첨단컴퓨터의 세계, 전자신문사, 1994.
● 참고 사이트
○ http://blog.naver.com/jkjang46.do?Redirect=Log&logNo=40002003851튜링머신
○ http://blog.naver.com/elysionfv.do?Redirect=Log&logNo=100003086370튜링머신을 개발한 앨런 튜링
○ http://cafe.naver.com/sylee999.cafe?iframe_url=/ArticleRead.nhn%3Farticleid=27 현대 컴퓨터의 아버지 앨런 튜링
○ http://www.ptuniv.ac.kr/~dhyang/lectures/formallanguage/at/auto9.hwp튜링머신의 7가지요소
○ http://windshoes.hihome.com/person-turing.htm 튜링머신의 정의 및 설명

키워드

튜링머신,   튜링,   머신,   구조,   영향,   Machine,   Turing,   기능