유한 오토마타와 튜링머신의 차이

유한 오토마타와 튜링 머신의 주요 차이는 다음과 같습니다.

1. 기억 장치(메모리)

유한 오토마타

유한 개의 상태(state)만 존재하고 추가적인 무제한 기억 장치가 없습니다.

상태의 개수가 유한하므로 기억 용량이 제한되어 있습니다.


튜링 머신

무한한 길이의 테이프를 기억 장치로 사용하며, 읽고 쓰기가 모두 가능합니다.

무제한의 기억 용량을 가집니다.



2. 전이와 동작 방식

유한 오토마타

입력 문자열을 왼쪽에서 오른쪽으로 한 번만 읽습니다.

입력 문자열을 다시 읽거나 수정할 수 없습니다.


튜링 머신

테이프 위의 정보를 양방향으로 이동하며 여러 번 읽고 쓸 수 있으며, 테이프 위 내용을 수정할 수 있습니다.



3. 인식 가능한 언어의 범위

유한 오토마타

정규 언어(regular language)만 인식 가능합니다.


튜링 머신

재귀적으로 열거 가능한(recursively enumerable) 언어를 포함하여 계산 가능한 모든 언어를 인식할 수 있습니다.

훨씬 더 강력한 계산 능력을 가집니다.



4. 계산 능력과 복잡성

유한 오토마타

단순한 계산만 가능하며, 계산 능력에 명확한 한계가 있습니다.


튜링 머신

현대 컴퓨터와 동등한 계산 능력을 가지며, 원리적으로 모든 가능한 알고리즘적 계산을 수행할 수 있습니다.



정리하면:

즉, 튜링 머신은 유한 오토마타보다 강력한 계산 능력을 가지며, 실제 현대 컴퓨터의 동작 원리를 설명하는 기본적인 이론 모델입니다.