튜링 기계의 기본 아이디어는 무엇입니까

튜링 기계의 기본 아이디어는 기계를 사용하여 사람들이 펜과 종이를 사용하여 수학적 연산을 수행하는 과정을 시뮬레이션하는 것입니다. 이 과정은 두 가지 간단한 작업으로 볼 수 있습니다. 1. 종이에 특정 기호를 쓰거나 지우는 것 2. 종이의 한 위치에서 다른 위치로 주의를 옮기는 것.

이 문서의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

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

Turing의 기본 아이디어는 사람들이 종이와 펜을 사용하여 수학 연산을 수행하는 과정을 시뮬레이션하는 것입니다.

1. 특정 기호를 쓰거나 지우는 것입니다.

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

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

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

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

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

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

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

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

프로그래밍 학습에 대해 더 자세히 알고 싶다면 php training 칼럼을 주목해주세요!

위 내용은 튜링 기계의 기본 아이디어는 무엇입니까의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!