오토 마 튜링

Question

누군가 단계별로 질문을 설명해 주시겠습니까?

Σ는 유한 집합이라고 가정하고 L1, L2 및 L3는 Σ 허용 가능한 서브셋 튜링 것을^* 다음 특성을 만족한다 : ∪ L1 L2 L3 = Σ ∪^* 단계; L1 ∩ L2 = L2 ∩ L3 = L3 ∩ L1 = ∅. L1, L2 및 L3 모두 모두 재귀 적이어야 함을 보여줍니다.

Answer 1

우리는 주어진됩니다

L1 union L2 union L3 = E* 
L1 intersect L2 = {} 
L1 intersect L3 = {} 
L2 intersect L3 = {} 
L1 is acceptable/semidecidable/recursively enumerable/recognizable 
L2 is acceptable/semidecidable/recursively enumerable/recognizable 
L3 is acceptable/semidecidable/recursively enumerable/recognizable 

우리는 L1, L2 및 L3는 rejectable 것을 보여줄 필요가/decidable/공동 인식/재귀.

문자열이 L1에 없음을 보여줄 수 있습니까? 예. 이 세 언어의 결합에는 모든 문자열이 들어 있기 때문에 두 언어가 겹치지 않기 때문에 L1에없는 문자열은 모두 L2 또는 L3에 있음을 알 수 있습니다. 이러한 언어는 수용 가능/반출 가능/재귀 적으로 열거 가능/인식 가능하기 때문에 TM2 및 L3에서 각각 문자열을 받아들이거나 결정하거나 열거/인식 할 TM2 및 TM3이 있습니다. 문자열이 L1에 있지 않다는 것을 인식하기 위해 T2와 T3을 실행하도록 설정하고 어느 쪽이든 문자열을 수락/결정/열거/인식하는지 여부를 확인할 수 있습니다.이 경우 L1은 그렇지 않아야합니다.

이제는 L1이 허용 가능/재귀 적으로 열거 가능/인식 가능하고 동시에 거부 가능/동시 반복적으로 열거 가능/공동 인식 가능하다는 것을 알았습니다. 이와 같은 언어는 결정 가능/재귀 적입니다.

L1, L2 및 L3에 임의로 번호가 지정 되었기 때문에 L1에 적용되는 결과는 L2 및 L3에도 적용되어야합니다. 다른 언어도 L1으로 간주 할 수 있기 때문입니다. 즉, L1을 L2 또는 L3으로 바꾸면 위에 주어진 것과 정확히 같은 인수가 적용됩니다.

따라서 세 가지 언어 각각은 결정 가능/재귀 적입니다.