1
튜링 인식 또는 공동 튜링 인식
하지만이 언어는 튜링 (Turing)으로 인식 할 수 있습니까? 아니면 공동 튜링으로 인식 할 수 있습니까?
A
답변
1
TM이 언어의 모든 문자열에서 중지를 허용 할 수있는 경우 언어는 RE입니다. 언어가 아닌 모든 문자열에서 TM이 중단 될 수있는 경우 언어는 동일합니다. L이 RE 인 경우 w을 수락하면 TM은 항상 w^R을 수락한다는 것을 알 수 있어야합니다. L이 coRE 인 경우 TM은 일부 w을 수락하지만 해당 w^R은 수락 할 수 있어야합니다. 그것은 RE도 coRE도 아니다.
특정 TM가 빈 언어를 받아들이는 일 때문에 경우 RE, 따라서
L에 속하는되지 않으며,이 사실을 인식 할 수있는 방법이 없습니다. 우리 언어에 대한 인식자는 빈 언어를 받아 들일 수없는 TM을 인식 할 수있게합니다.특정 TM이 하나의 팔린 드롬이 아닌 문자열로 구성되어 있기 때문에
L에 속하지 않는 경우이 사실을 인식 할 수 없기 때문에 coRE가 아닙니다. 우리 언어에 대한 인식자를 사용하면 단일 회문이 아닌 문자열을 사용할 수있는 TM을 인식 할 수 있습니다.