튜링 기계는 컴퓨터인가?

튜링 기계는 컴퓨터인가요?

튜링 기계는 컴퓨터가 아니라 단지 이론적인 컴퓨팅 모델일 뿐입니다.

튜링 기계는 무한히 긴 종이 테이프를 가지고 있는 추상 기계를 말합니다. 종이 테이프는 작은 사각형으로 나누어져 있으며 각 사각형은 서로 다른 색상을 가지고 있습니다. 종이 테이프 위에서 움직이는 머신 헤드가 있습니다. 머신 헤드에는 일련의 내부 상태와 일부 고정된 절차가 있습니다. 매 순간 머신 헤드는 현재 종이 테이프에서 사각형의 정보를 읽은 다음 자체 내부 상태를 기반으로 프로그램 테이블을 검색하고 프로그램에 따라 정보를 종이 테이프 사각형에 출력하고 자체 내부 상태를 변환해야 합니다. 을 선택한 다음 이동합니다.

1936년 영국의 수학자 앨런 매더슨 튜링(1912-1954)은 추상 컴퓨팅 모델인 튜링 기계를 제안했습니다. 튜링 컴퓨터라고도 알려진 튜링 머신은 사람들이 종이와 연필을 사용하여 수학적 연산을 수행하는 과정을 추상화하고 가상 머신이 인간을 수학적 연산으로 대체합니다.

기본 아이디어

Turing의 기본 아이디어는 사람들이 종이와 펜을 사용하여 수학적 연산을 수행하는 과정을 기계를 사용하여 시뮬레이션하는 것입니다. 그는 이러한 과정을 다음 두 가지 간단한 작업으로 간주했습니다.

1. 또는 기호를 지우세요.

2. 종이의 한 위치에서 다른 위치로 주의를 이동하세요.

각 단계에서 사람은 (1) 종이에서 현재 주의를 기울이고 있는 특정 위치의 기호와 (2) 사람의 현재 사고 상태에 따라 다음 행동을 결정해야 합니다.

인간의 계산 과정을 시뮬레이션하기 위해 Turing은 다음과 같은 부분으로 구성된 가상의 기계를 만들었습니다.

1. 무한히 긴 종이 테이프. 종이 테이프는 차례로 작은 격자로 나누어져 있으며, 각 격자에는 제한된 알파벳의 기호가 포함되어 있으며, 알파벳에는 공백을 나타내는 특수 기호가 있습니다. 종이 테이프의 격자선은 왼쪽에서 오른쪽으로 0, 1, 2,...의 번호가 매겨져 있으며, 종이 테이프의 오른쪽 끝은 무한히 확장될 수 있습니다.

2. 읽기-쓰기 헤드 HEAD. 읽기/쓰기 헤드는 종이 테이프에서 왼쪽과 오른쪽으로 이동할 수 있으며 현재 가리키는 그리드의 기호를 읽고 현재 그리드의 기호를 변경할 수 있습니다.

3. 일련의 제어 규칙 표. 기계의 현재 상태와 현재 읽기/쓰기 헤드가 가리키는 그리드의 기호를 기반으로 읽기/쓰기 헤드의 다음 동작을 결정하고 상태 레지스터의 값을 변경하여 기계가 새로운 상태에 들어가도록 합니다. .

4. 상태 레지스터. Turing Machine의 현재 상태를 저장하는 데 사용됩니다. 튜링 기계의 가능한 모든 상태의 수는 유한하며 정지 상태라는 특별한 상태가 있습니다. 종료 문제를 참조하세요.

이 기계의 모든 부분은 유한하지만 잠재적으로 무한한 길이의 종이 테이프를 가지고 있으므로 이 기계는 이상적인 장치입니다. Turing은 그러한 기계가 인간이 수행할 수 있는 모든 계산 과정을 시뮬레이션할 수 있다고 믿었습니다.

일부 모델에서는 읽기/쓰기 헤드가 고정된 종이 테이프를 따라 움직입니다. 수행할 명령(q1)이 읽기/쓰기 헤드에 표시됩니다. 이 모델의 "빈" 테이프는 모두 0입니다. 읽기-쓰기 헤드에 의해 스캔된 공백, 1, 1, B로 표시된 사각형 및 읽기-쓰기 헤드 기호를 포함하여 음영 처리된 사각형은 시스템 상태를 구성합니다. (Minsky의 그림(1967) p.121).

위 내용은 튜링 기계는 컴퓨터인가?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!