-2
L:={<M>|HP<=L(M)}이 재귀 언어인지 여부와 재귀 적으로 열거 가능한 언어 인 L인지 확인해야합니다.언어 분류 (계산)
나는 L이 L이 중 R에없는 다음 RE에없는 경우 쌀의 정리 ... L가 순환되지 증명하지만 L 재귀 열거이라고 생각하지 않습니다
A
답변
0
도움을 줄 수 있다고 생각합니다.
중단 문제로 축소해야합니다. X는 L (X)가 참이면 거짓을 출력하고 L (X)가 거짓이면 참을 출력하는 튜링 기계라고 말할 수 있습니다.
L (X)이 true입니까? L (X)가 거짓 일 경우에만 그것은 모순이다.
L (X)가 거짓입니까? L (X)가 참인 경우에만 해당되며, 이는 모순이기도합니다.
모순은 L이 튜링 기계에 의해 계산 될 수 있다는 암묵적인 가정에 있습니다. 따라서 L은 계산할 수 없습니다. X 튜링 기계는 존재할 수 없습니다. 마지막으로 L은 RE에 없으며 R에도 없습니다.
여기에 HP가 무엇을 의미합니까? –