튜링 머신이 단어를 수락하기 전에 최소한 K> 2 상태를 통과하는지 확인하십시오.

Question

$ l=\ \ langle m, k \ rangle \ mid \ in l (m) \ text {\ $ m $가 적어도 $ k> $ w $} \} $

를 수락하기 전에 2 $ 별개의 상태

나는이 언어가 RE 또는 핵심이 아니라는 것을 증명하기 위해 감소를 생각하려고 노력한다. 이 문제에 어떻게 접근하는 방법?힌트 또는 직감이 있습니까?

나는 보통 쌀을 사용할 수 있는지 여부를 확인하지만 여기에있는 질문은 언어 그 자체에 관한 것이 아닙니다

Answer 1

명확하게 $ l $ 은 허용됩니다 ( $ m $ 을 시뮬레이션하고 숫자를 추적하십시오 시뮬레이션 중에 발생한 별개의 상태). 우리는 이제 그것이 아밀리가 아님을 보여줍니다.

$ l $ 이 디지털이면 다음과 같이 멈춤 문제를 해결할 수 있습니다. TM $ T $ 및 입력 $ x \ sigma ^ * $ , TM을 구성하십시오 $ M $ 은 입력 $ T $ 을 시뮬레이트합니다. "> $ x $ 및 시뮬레이션이 완료되면 수용됩니다. $ m $ 이 허용되는 경우, 적어도 $ 3 $ 별도의 상태로 이송되도록 더욱 보장 할 수 있습니다. $ T $ 의 시뮬레이션을 시작하기 전에 초기 상태로부터 다른 (별개의) 상태로 전환함으로써.

이제 $ \ langle m, 3 \ rangle \ l $ 인지 확인하십시오. 대답이 긍정적 인 경우 $ m (w)에 대한 $ w \ \ sigma> $ 이 있습니다. $ 은 $ t (x) $ 멈춤을 보여줍니다. 대답이 음수이면 $ M $ $ t (x) $ 이 표시되지 않음을 보여줍니다. 멈추다.