튜링 기계
위키백과 ― 우리 모두의 백과사전.
튜링 기계 (Turing machine)란 컴퓨터의 실행과 저장에 관한 추상적인 모델로서 1936년에 앨런 튜링이 알고리즘에 대한 엄밀한 수학적 정의를 위해 도입한 개념이다. 이 개념은 컴퓨터 과학 이론에서 널리 사용되고 있는데, 특히 계산 복잡도 이론과 계산이론에서 아직도 널리 사용되고 있다. 튜링 기계가 논리나 수학에서 사용될 수 있는 체계의 뭉뚱그려진 개념까지도 모두 온전히 묘사할 수 있다는 명제는 처치-튜링 명제로 알려져 있다.
튜링 기계의 개념은 '한정된 숫자의 기호 가운데 하나를 가질 수 있는 칸이 무한히 늘어서 있는 종이의 내용을, 엄밀하게 정의된 절차에 따라 규칙적으로 바꿈으로써 계산을 행하는 사람'에 관한 발상을 바탕으로 한다. 이 사람은 종이가 가질 수 있는 한정된 숫자의 '상태'를 종류별로 기억해야 하며 계산 절차는 “현재 상태가 42이고 지금 보이는 기호가 '0'이면 이것을 '1'로 바꾸고 기호 하나를 오른쪽으로 옮긴 뒤 현재 상태를 17로 지정하라”와 같이 매우 기본적인 단계들에 의해 공식화된다.
튜링 기계는 인공지능의 개념을 밝히고자 튜링이 발표한 튜링 테스트와 간혹 혼동되기도 하지만 이 둘은 별개의 개념이다.
다른 모든 튜링 기계를 흉내낼 수 있는 튜링 기계는 범용 튜링 기계(universal Turing machine) 또는 범용 기계라고 부르며 그 이유는 튜링이 1947년에 이 기계를 다음과 같이 묘사했기 때문이다.
- 이런 종류의 기계는 단 하나만 있어도 모든 일을 수행할 수 있다는 점이 확인된다. 이것은 사실 얼마든지 다른 모든 기계의 모델이 될 수도 있다. 이 특수한 기계는 범용 기계라고 불리어야 할 것이다.
[편집] 참고
| 오토마타 이론: 형식 언어 및 형식 문법 | |||
|---|---|---|---|
| 촘스키 위계 | 형식 문법 | 형식 언어 | 최소한의 자동장치 |
| Type-0 | (무제약) | 순환 열거 언어 | 튜링 기계 |
| (무제약) | 순환 언어 | 판정자 | |
| Type-1 | 문맥 의존 문법 | 문맥 의존 언어 | 선형유한 오토마타 |
| Type-2 | 문맥 무관 문법 | 문맥 무관 언어 | 내리누름 오토마타 |
| Type-3 | 정규 문법 | 정규 언어 | 유한 오토마타 |
| 각 언어 및 문법은 바로 윗 줄 언어 및 문법의 진부분집합이다. | |||
 |
이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
