Turing machine (튜링 기계)

소개

Turing machine (튜링 기계) 에 대해 간략 하게 기술 하였다.
인터넷의 자료를 간략 하게 정리 해 두었습니다.

목차

1. Introduction
2. Informal description
3. Examples of turing machines
4. Formal definition
5. Additional details required to visualize or implement Turing machines
5.1. Alternative definitions
5.2. The "state"
5.3. Turing machine "state" diagrams
6. Models equivalent to the Turing machine model
7. Choice c-machines, Oracle o-machines
8. Universal Turing machines
9. Comparison with real machines
9.1. Limitations of Turing machines in computational complexity theory

본문내용

1. Introduction
1936년 Alan Turing이 On computable Numbers, with an Application to the Entscheidungsproblem 라는 논문에서 소개한 당시로서는 실제 기계가 아닌 추상적인 수학 개념의 오토마타 이었다.
튜링기계는 임시 저장장소가 테이프인 오토마타 (Automata) 이다. 이 테이프는 셀들로 나뉘어 있고, 각 셀은 한 개의 심볼을 저장할 수 있다. 이 테이프와 관련해서 읽기-쓰기 헤드(read-write head) 가 있다. 이 읽기-쓰기 헤드는 테이프에서 왼쪽 또는 오른쪽으로 움직일 수 있고 각 이동마다 하나의 심볼을 읽고 쓸 수 있다. 우리는 튜링 기계를 오히려 간단한 컴퓨터로 생각할 수 있다. 간단한 컴퓨터는 유한한 메모리를 갖는 처리 유닛 (processing unit) 을 가지고 있고, 테이프에, 무제한 양의 보조 저장장소를 가지고 있다. 그런 컴퓨터가 수행할 수 있는 명령어들은 극히 제한되어 있다. 이러한 작은 명령어들의 집합은 복잡한 일을 하기에 적절하지 않은 것처럼 보이나, 그러나 그렇지 않다. 튜링 기계는 원칙적으로 아주 강력하다. (Peter Linz 2001)

튜링 `기계` 에 대해서 우선 염두에 두어야 할 사항은 그것이 실제 기계가 아니라 하나의 `추상 수학 개념` 이라는 것이다. 이 개념은 영국의 수학자요 암호 해독 전문가며 컴퓨터의 대가로 알려진 Alan Turing 이 결정문제(Entscheidungsproblem)으로 알려진 아주 광범위한 수학 문제를 해결하기 위하여 1936 년에 소개한 개념이다. 이 문제는 독일의 유명한 수학자 David Hilbert 가 1900 년 파리 국제수학회에서 일부 제기한 문제로서 힐베르트의 열 번째 문제라고도 불리는데 이 문제의 완전한 형태는 1928 년 볼로냐 국제학회에서 제시되었다. 힐베르트가 제기한 문제는 매우 엄청난 것이었는데 그것은 모든 수학 문제들을 풀 수 있는 일반적 알고리즘을 찾아 내는 것이었다. 더 엄밀히 말하면 그러한 알고리즘이 (기계가) 원칙적으로 존재할 수 있는가 하는 것에 대한 해답을 구한 것이다.
이 문제를 대답하는 데 어려운 점 중의 하나는 도대체 `기계적 프로그램` 의 정확한 의미가 무엇인가를 결정하는 것일 것이다. 그 개념은 당시 일반적인 수학적 개념의 한계를 넘어선 것이었다. 그 개념을 수식화하기 위하여 튜링은 기계 동작을 기본적인 식으로 나누어 정형화함으로써 `기계` 라는 개념이 어떻게 수식으로 표현될 수 있는가를 보이려고 하였다. 튜링은 인간의 뇌(Brain)도 하나의 `기계` 로 간주하였다. 그러므로 수학 문제를 푸는 수학자의 행동이 무엇이건 그것이 `기계적 프로그램` 으로 표시될 수 있다고 생각하였다. (Roger Penrose 1989)

참고자료

· 없음