튜링 머신(Turing machine)

간단요약:
1936년에 Turing이 고안한 추상적 계산 기계. 튜링 머신은 순서에 따라 계산이나 논리 조작을 행하는 장치로, 적절한 기억 장소와 알고리즘만 주어진다면 어떠한 계산이라도 가능함을 보여 주어 현대 컴퓨터의 원형을 제시하였다. 그러나 튜링 머신은 직렬 방식 계산의 단순성, 범용성과 함께 직렬 방식으로 처리되기 어려운 함수가 존재할 수 있음도 보여 주었다.

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

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

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

튜링 머신(Turing machine)은 오토마타(Automata)중 하나이다. 
오토마타란 규칙에 의해 움직이는 논리적 장치를 말한다. 수학자이자 현대 컴퓨터의 아버지인 앨런 튜링이 창안한 개념으로 현대의 모든 계산 가능한 기계는 튜링 머신으로 환원할 수 있다.(*) 말하자면 계산 가능한 모든 함수/기계/논리/알고리즘 의 원자적인 개념이다.
계산 이론(Theory of computation)에는 튜링 머신 말고도 하등한 머신이 더 있다. 이미 학자들에 의해 튜링 머신과 푸쉬다운머신과 같은 오토마타들 사이를 수학적으로 분류하였다. 그 중에 튜링머신이 가장 높은 호환성을 지니고 있다.

튜링 머신은 그림과 같이 이루어져 있다. 무한한 길이의 테이프 기록 장소, 1개의 읽기/쓰기 헤드, 헤드는 테이프를 따라 움직일 수 있고, 컨트롤 유닛은 테이프의 현재 셀에 기록된 0,1의 숫자와 내장된 그래프에 따라서 어떻게 읽고 이동할지를 결정한다.

이 간단해보이는 장치가 복잡한 함수/기계/논리/알고리즘을 환원할 수 있다.(*) 따라서 튜링머신으로 풀 수 없는 문제는 어떤 컴퓨터로도 풀 수 없다. 무제한의 메모리를 주어도 양자컴퓨터조차 튜링 머신과 동등하다. 

 
 
출저:http://skeptic.cynical.kr/4713739

찬웅이형이 알려준 튜링머신
좀 궁금해서 구글링해서 퍼옴 ㅎㅎㅎ