중화사전망 - 자전 검색 - 영감은 "언어" 요약을 받아들입니다.
영감은 "언어" 요약을 받아들입니다.
열거자 E 는 임의의 순서로 언어 L(E) 을 열거할 수 있으며 L(E) 의 문자열은 E 에 의해 여러 번 중복 인쇄될 수 있습니다.
튜링 인식 언어의 정의: m 을 튜링기로 설정하십시오. M 이 입력 문자열 ω에서 실행 후 수락 상태로 들어가 중지할 수 있는 경우 M 수락 문자열 ω 라고 합니다. M 이 허용하는 모든 문자열의 집합을 m 인식 언어 (L(M) 라고 합니다.
S 를 설정하시겠습니까? σ * 는 언어입니다. L(M)= S 를 만드는 튜링 기계 m 이 있다면 튜링 기계 m 인식 s, s 를 튜링 인식 언어라고 합니다.
다음 정리는 재귀 열거형 언어와 튜링 인식 언어 간의 관계를 보여 줍니다.
정리: 언어는 튜링이 인식할 수 있고 재귀적으로 열거할 수 있는 경우에만 가능합니다.
증명: 열거 언어 S 에 대한 열거자 E 가 있는 경우 튜링 기계 M 을 다음과 같이 구성합니다.
M = 입력 ω 의 경우
E 를 실행하여 문자열 S 1, S2, ...;
Si =ω 가 발생하면 수락 상태로 들어가 중지됩니다.
주의하면 오메가? S, M 은 결코 멈추지 않을 수도 있지만 M 이 허용하는 단어 세트는 정확히 S 이므로 M 은 S 를 인식합니다. .....
튜링 기계 M 인식 언어 S 가 있고 다음과 같이 열거자 E 를 구성한다고 가정해 봅시다.
E = 입력 무시.
I = 1, 2,3 에 대해 다음 단계를 반복합니다.
σ * = {S 1, S2, ...}, 각각 s 1, S2, ..., si 를 m 의 입력으로 사용하고 m 을 시뮬레이션하여 I 단계를 수행합니다.
Sj, 1 ≤ j ≤ I 가 단계 I 의 M 에 의해 받아들여질 수 있다면 출력합니다.
이런 방식으로 구성된 열거자 E 의 최종 출력 언어는 정확히 S 입니다. S 의 문자열은 E 에서 사전 순서로 출력되지 않으며 동일한 문자열은 E 에 의해 여러 번 출력될 수 있지만 열거자의 정의에 따라 허용됩니다.
튜링 인식 언어와 튜링 인식 언어의 차이점을 확인합니다. S 가 튜링 인식 언어인 경우 하나의 튜링 기계 M 만 있습니다. M 이 ω S 를 입력하면 M 이 멈추고 수락 상태로 들어갑니다. M 의 입력이 ω 일 때? S, M 은 중지하고 거부 상태로 들어가거나 결코 멈추지 않을 수 있습니다.
그러나 S 가 튜링 판정 언어, 즉 재귀 언어라면 튜링 기계 M 이 있어야 입력 문자열 ω 에 대해? σ *, M 은 S 가 수락 또는 거부 상태에 속하는지 여부에 따라 계속 멈출 수 있습니다.
모든 언어가 튜링이 인식할 수 있는 것은 아니다. 이것은 튜링이 인식할 수 없는 언어의 존재를 증명할 수 있다.
가동 중지 시간 문제는 모든 프로그램이 제한된 시간 내에 실행을 끝낼지 여부를 판단하는 것입니다.
이 문제는 주어진 프로그램 P 와 입력 W, 프로그램 P 가 입력 W 에서 최종적으로 중지될 수 있는지 (무한 루프에 들어가지 않고) 를 결정하는 것과 같습니다.
수학어로 설명하자면, 그 본질적인 문제는 튜링기 T 와 임의의 언어 세트 S 가 주어지면 T 는 결국 모든 오메가 S 에서 멈출까요? 그 의미는 식별 가능한 언어의 의미와 같다. 분명히, 모든 제한된 S 는 확실하고, 셀 수 있는 S 도 멈출 수 있다.
애륜 튜링은 1936 에서 종료 문제를 해결하는 일반적인 알고리즘이 없다는 것을 증명했다.
추치 튜링 논점은 "어떤 알고리즘에서든 계산할 수 있는 문제는 튜링기로 계산할 수 있다" 고 주장했다.
또 다른 주장은 논리와 수학에서 유효하거나 기계적인 방법이 튜링기로 표현될 수 있다는 것이다. 일반적으로 이러한 방법이 다음 요구 사항을 충족해야 한다고 가정합니다.
1. 메서드는 제한된 수의 기호로 설명할 수 있는 간단하고 정확한 지시문으로 구성됩니다.
이 방법은 항상 제한된 단계에서 결과를 생성합니다.
기본적으로 사람들은 종이와 연필로만 그것을 완성할 수 있다.
4. 이 방법의 실현은 인간의 지혜가 이러한 지시들을 이해하고 집행할 필요가 없다.
이 방법의 한 가지 예는 유클리드 나눗셈을 통해 두 자연수의 최대 공약수를 결정하는 것이다.
허용되는 문자열 세트가 σ 인 재귀 언어 L 이 있다고 가정합니다. 검증: l: σ * \ l 의 보완 세트도 반복 언어입니다.
증명 절차:
L 은 재귀 언어이기 때문에 튜링 기계 M 1 이 있습니다. 이 기계는 다음과 같이 할 수 있습니다.
1. 그리고 ω σ * andl 인 경우에만 입력 문자열 ω가 수락되고 항상 종료 상태로 들어가는 것이 최종 상태입니다.
ω σ * 및 ω 만? L, 입력 문자열 ω가 거부되어 항상 닫힌 상태로 들어갑니다. 이는 최종이 아닙니다.
이제 M 1 의 최종 상태와 비최종 상태 (원래 비최종 상태는 최종 상태가 되고 최종 상태는 비최종 상태가 됨) 를 교환하여 또 다른 튜링 기계 M2 를 구성합니다. M2 는 다음과 같은 작업을 수행할 수 있습니다.
1. 입력 문자열 ω가 수락되고 ω * and σ * \ l 인 경우에만 종료 상태로 들어가는 것이 최종 상태입니다.
ω σ * 및 ω 만? σ* \ L, 입력 문자열 ω가 거부되었습니다. 항상 꺼짐 상태로 들어갈 수 있습니다. 이는 최종이 아닙니다.
따라서 M 1 에 의해 거부된 입력은 M2 에 의해 수락되고 M 1 에 의해 수락된 입력은 M2 에 의해 거부됩니다.
M2 는 σ * \ l 만 허용합니다. 즉 σ * \ l 도 재귀 언어입니다.