Turing-Recognizable 언어의 클래스가 보완하에 닫히지 않는 이유는 무엇입니까?

Question

저는 튜링 머신을 공부하고 있습니다. 이미 유니온, 교차, 병합, 보완 및 클라인 스타의 운영을 위해 Turing-Decidable이 어떻게 닫혀 있는지 보여 줬습니다. 다음으로 T-Recognizable 언어가 Union, Intersection, Concatenation 및 Kleene Star에서 어떻게 닫혀 있는지 보여주는 몇 가지 데모를했습니다.

저는 T- 인식 가능한 언어의 분류가 보완 작업을 위해 닫히지 않는 이유를 보여주기 위해 질문에 대답하려고하지만 이해할 수 없습니다. 누군가 설명해 주시겠습니까?

감사

Answer 1

1. T-recog 세미 decidable (R.E.)에 대응한다.

2. 언어 자체와 상대적인 보수가 모두 r.e. 인 경우 언어가 정확하고 결정할 수 있다고 확신하십시오.

3. r.e. 결정할 수없는 언어들 (예 : Halt 문제점)

4. r.e. 언어는 보완하에 닫히고 2와 3에서 언급 한 사실에 대한 모순을 유도합니다.