계산 모델과 계산 이론

여러 계산모델

1. 튜링 기계 turing machine

- read, write head가 스캐닝 하는데로 사각형 무한 길이의 테이프 상에 문자를 저장

2. 재귀 함수 recursive function 

- 수에 관한 연산을 위해 함수와 함수의 조합 사용 

3. 람다 계산법 lambda calculus

4. 마르코브 알고리즘 markov algorithm

5. 포스트 시스템 post systems

 

 

 

처치-튜링 명제 church-turing thesis

- 위 형식 모델 formalisms들은 계산 능력에서 동등한것으로 봄

- 한 모델에서 수행가능한 계산을 다른 모델로도 수행 가능

- 그 모델들은 컴퓨터가 무한 메모리를 가진다면 보통 컴퓨터에서 동등한 능력을 보임

=> 처치-튜링 명제 : 알고리즘 개념이 적절히 형식화되면 모든 알고리즘은 튜링 머신에서 수행될수 있음

=> 계산 가능성 이론 : 어떤것이 기계로 계산될수 있는지 다룸

 

 

 

계산 이론의 연구

- 일반적인 계산 모델과 컴퓨팅 한계 연구

-> 어떤 문제가 컴퓨터로 해결 불가능한가? 

-> 컴퓨터로 해결 가능하지만 해법이 비현실적이여서 오랜 시간이 필요한가?

-> 주어진 해법을 확인하는 것 보다 문제 해결이 더어려울 수 있는가?(P와 NP)