계산 모델

계산 모델(model of computation)은 컴퓨터 과학, 특히 계산 가능성 이론과 계산 복잡도 이론에서 주어진 입력에 따라 수학 함수의 출력이 어떻게 계산되는지 설명하는 모델이다. 모델은 계산, 메모리 및 통신 단위가 어떻게 구성되는지 설명한다. 알고리즘의 계산 복잡도는 계산 모델을 통해 측정할 수 있다. 모델을 사용하면 특정 구현 및 특정 기술에 특정한 변형과 관계없이 알고리즘 성능을 연구할 수 있다.

모델

연속 모델

• 유한 상태 기계
• 푸시다운 자동 기계
• 레지스터 머신
  • 랜덤 접근 기계
• 튜링 기계

함수 모델

• 추상 재작성 시스템
• 조합 논리
• Μ-재귀 함수
• 람다 대수

동시성 모델

• 행위자 모델
• 세포 자동자
• 논리 회로
• 페트리 네트
• 프로세스 계산

같이 보기

• 스택 머신
• 누산기
• 레지스터 머신
• 랜덤 접근 기계
• 추상 기계
• 촘스키 위계
• 튜링 완전

출처

• Fernández, Maribel (2009). 《Models of Computation: An Introduction to Computability Theory》. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1. 
• Savage, John E. (1998). 《Models Of Computation: Exploring the Power of Computing》. Addison-Wesley. ISBN 978-0201895391.