AlanTuring이 고안한 오늘날 컴퓨터의 최초 수학적모델. 대표적인 FSA

현재우리가 쓰는 컴퓨터는 모두 이 모델을 따른다. AlanTuring은 이 발명으로 TuringAward을 설립한다.

그는 한 장의 테이프를 앞으로 보내고 뒤로 당기며 이 테이프에 기호를 쓰고 읽으며 지우는 기본적인 몇몇 동작만 할 수 있는 간단한 기호적 프로세서를 사용함으로써, 어떠한 논리적 또는 수학적 문제도 해결할 수 있다는 것을 증명하였는데 이 프로세서가 TuringMachine이다.

TuringMachine은 논리적 시스템으로 작업하는 사람이라면 수행할 수 있는 모든 연산을 수행할 수 있고, 컴퓨터 내부에서 이루어지는 계산과 수행을 튜링 기계 내부 동작으로 모형화시키는 것이 가능하다. 따라서, Algorithm은 프로그램 개발자의 추상적인 개념 그 자체이며, 이것을 실현할 수 있는 구체적인 수단은 TuringMachine와 같이 매우 간단한 구성의 기계로부터 충분히 가능하다.

이 모델은 polymonial한 문제는 빠르게 계산할 수 있으나, NP problem은 현실적으로 풀기가 어렵다. Bioinformatics의 문제 및 몇몇 문제들이 NP problem이기 때문에 이 한계점을 극복하고자, DnaComputer, QuantomComputer등의 연구가 진행중이다.

TuringMachine (last edited 2012-01-16 13:45:59 by 211)

web biohackers.net