다음 언어는 왜 결정 불가능합니까?

Question

저는 현재 이번 학기 시험을 위해 공부하고 있으며 지난 몇 년간의 오래된 시험을 해결하려고 노력했습니다.

문제는 L이 결정 불가능하다는 것을 보여주는 것입니다.$L=\{w|T(M_w) eq\emptyset \land \forall x \in T(M_w):xx\in T(M_w)\land xxx otin T(M_w)\}$

언어를 보여줬어요 $ l '= {w | t (m_w) neq emptyset } $ 라이스 정리(Rice Theorem)로 인해 결정이 불가능하다.나는 Turing Machines를 만들었습니다. $M_1$ ~와 함께 $T(M_1)=\빈 집합$ 그리고 $M_2$ ~와 함께 $T(M_2)=\시그마^*$ L'이라는 언어가 사소하지 않다는 것을 보여주기 위해서입니다.(부터 $1\L$ 그리고 $2 otin A$.일반성을 잃지 않고 해당 기계에 Gödelindexes 1과 2가 있다고 가정합니다.

이제 내 문제는 이 결과가 언어 L로 전달된다는 것을 보여줄 방법이 없다는 것입니다.나는 언어 L이 그러한 괴델 색인만을 포함해야 한다는 것을 알고 있습니다. 그러한 색인에 대해 다음 TM은 무한한 단어를 허용해야 합니다(왜냐하면 $x\in T(M_w)$ 있어야 한다 $xx\in T(M_w)$...그러므로 반드시 $xxxx\in T(M_w)$ 등.)

제안/답변을 듣고 싶습니다!미리 감사드립니다

Answer 1

이는 라이스 정리의 직접적인 결과입니다.단어 $w$ 에 있습니다 $L$ 만약에 $T(M_w)$ 다음 의미론적 특성을 만족합니다.

$T(M_w)$ 비어 있지 않으며 어떤 경우에도 $x \in T(M_w)$, 우리는 $x^2 ​​\in T(M_w)$ 그리고 $x^3 otin T(M_w)$.

라이스의 정리에 따르면 이 언어가 결정 불가능하다는 것을 보여주기 위해 두 대의 튜링 기계를 전시해야 합니다. $w_1$ 그리고 $w_2$:하나는 속성을 만족하지 않고 다른 하나는 속성을 만족합니다.우리는 걸릴 수 있습니다 $w_1$ 그런 기계가 되려면 $T(M_{w_1}) = \빈 집합$, 그리고 $w_2$ 그런 기계가 되려면 $T(M_{w_2}) = \{ a^{2^n} :n \geq 0 \}$.