튜링기계

요약 영국의 수학자인 A.M.튜링에 의해 고안된 가상(假想)의 자동기계.

튜링은 1936년 발표한 논문에서 추상적인 기계(이론상의 계산기계)를 정의하였는데, 이 기계는 유한상태의 기계로서 테이프를 가지고 있고, 테이프에는 부호를 기록하여 이를 다시 읽을 수 있으며, 또 이 부호를 변경할 수도 있고, 테이프를 앞뒤로 움직일 수도 있는 간단한 기계이다. 따라서 다음의 입력은 다른 장소에 오게 된다. 그러므로 이 기계는 초보적인 와 각 상태에 따른 내부기억능력을 보유하고 있다.

이 기계가 할 수 있는 일은 지극히 제한되어 있으나, 상당히 복잡한 계산을 할 수 있다. 튜링기계의 종류는 다양하며, 이 중에 다른 어떤 기계의 조작도 흉내낼 수 있는 기계가 존재한다. 자체가 유한의 기억장치를 가지고 있으며, 이러한 무한기계를 연구하는 이유는 우선 유한상태의 기계에서도 기억장치가 현실적으로 커지고 있다. 따라서 새로운 일을 하려면 점차적으로 이를 확장해야 한다.

그러므로 우선 튜링기계가 무한정의 테이프를 가지고 있다고 생각하지 않고, 유한하다고 생각한 후에 테이프가 모자라면 추가한다고 생각하면 실제의 경우와 부합하게 된다. 이러한 생각이 현재의 컴퓨터와 이론적인 기초를 생각한 것으로 평가되고 있으며, 그 이론은 컴퓨터나 의 설계 등에 큰 도움을 주고 있다.