이 언어는 결정 가능하고 인식 가능하며 인식 할 수 없습니까?

Question

M이 허용하는 언어가 유한 한 모든 튜링 기계 설명 M으로 구성된 언어 L입니다.

나는 M이 시작과 수락 상태 사이에 루프가 존재하면 거짓을 반환하고 그렇지 않으면 true를 반환하는 함수 D (M)에서 M을 실행할 수 있기 때문에 L은 결정할 수있는 언어라고 말했다.

나는 무한 루프를 감지하는 어려움을 과소 평가하기 때문에 내가 틀렸다는 느낌이 들었습니다.

지원을 부탁드립니다. 미리 감사드립니다.

Answer 1

이 언어를 결정할 수 있으면 중단 문제를 결정할 수 있습니다.

M이 기계이고 x가 입력이라고 가정합니다. 중지 문제는 M이 x에서 정지하는지 여부를 말합니다. 테이프를 지우고 이전에 입력 된 것이 무엇이든간에 x를 쓰는 기계 N을 고려하십시오. 이제 N을 실행 한 다음 M을 실행하여 얻은 기계를 고려하십시오.이 기계는 M이 x를 승인하면 모든 입력을 승인하고, 그렇지 않으면 입력을 승인하지 않습니다. 언어가 허용되는지 여부에 관계없이 모든 기계에 대해 말할 수 있다면 M이 x에 정지하는지 여부를 말할 수 있습니다. 하지만 그게 문제였습니다.