1. 계산 기계 (Computational Machine) 이란?
ㅇ 컴퓨터에 대한 수학적/추상적 모델화에 따른, 호칭
- 즉, `계산할 수 있는 것`에 대한 수학적 정의
- 결국, `계산이란 무엇인가?`라는 질문에,
. 답을 제시할 수 있는, 수학적 기초를 마련하고,
. 이를 구현하는 방법을 찾으려고 하는 것임
※ 1930년대에, 쿠르트 괴델(Kurt Gödel), 알론조 처치(Alonzo Church), 에밀 포스트(Emil Post),
앨런 튜링(Alan Turing) 등에 의해 연구됨
2. 튜링 머신 (Turing Machine) 이란?
ㅇ 프로그램화될 수 있는 계산 기계
- 기억 영역을 갖고 분명한 답이 있는 계산을 할 수 있는 것
ㅇ 컴퓨터의 이론적 모델
- 계산 기계에 대한 가상적인 모형
ㅇ 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸어,
기계적 계산 원리를 설명
ㅇ `계산가능함 (computability)`를 정의하는데 도움을 줌
※ 튜링 (Alan Turing, 1912-54) : 영국의 컴퓨터 과학자이자 수학자
3. 튜링 머신의 구성 요소 다섯(5)
ㅇ 테이프 : 무한 길이 (입력,저장장치)
- 기계가 인식하거나 기록할 수 있는 기호들이 저장됨
- 연산을 위해, 무한한 저장 공간을 가진 기계
ㅇ 기호 : 유한 종류 (알파벳 집합)
ㅇ 헤드 : 테이프를 이동하며, 기호를 읽고 쓸 수 있음 (CPU)
- 그 동작은 현재 상태와 읽은 기호에 따라 정해짐
. 같은 상태라도 읽은 기호에 따라 동작이 달라짐
ㅇ 상태 : 유한 종류 (유한 상태 집합)
ㅇ 규칙 : 상태,기호에 따른 헤드 동작을 정해 둔 것 (알고리즘)
※ 기호,상태,동작은, 모두 유한 이며, 이산적 이며, 구분 가능 함
※ 결국, 주어지는 테이프와 규칙에 따라 동작하는 기계 (추상적인 계산 기계 모형)
4. 튜링 머신의 종류
ㅇ 결정론적/비결정론적
- 결정론적 튜링 기계
. 오직 한가지 상태로 만 바뀔 수 있음 (순차 처리)
- 비결정론적 튜링 기계
. 1 이상의 상태로 바뀔 수 있거나, 바뀔 상태 없음 (병렬 처리)
ㅇ 만능 튜링 머신