다음 언어를 받아들이는 TM의 존재를 증명합니다

Question

나는 문제에 접근하는 방법에 대한 아이디어를 가지고 있지만 그것에 대해 확신하지 못합니다. 튜링 머신을 감안할 때, 나는 기계가있는 상태의 수를 확인할 수 있으며, 실행이 테이프의 끝없는 셀을 사용하는지 여부를 알 수있는 상태의 수를 확인할 수 있습니다. 그러나 나는 어떤 수의 국가 수와 내가 확인해야 할 일을 어떻게 사용할 수 있는지 모르겠다. 나를 혼란스럽게하는 것은 끝없는 루프를 입력하는 것이 반드시 필름의 끝없는 세포를 사용하는 것이 필요하지 않다는 것입니다.

$ L_K={ |\, m \, \, \, \, \, \, \, tm \, \, \, \, \, \, \, k \, \, tape\, \, \, \, \, \, 러닝 \, \, \, \, \, \, \ \, \} $

증명 : $ l ^ *=bigcup \ limits_ {k \, \ in \ mathbb {n}} l_k \, \ in \, \, \, \ setminus r $

Answer 1

언어 $ l ^ * $ 은 $ m $ 으로 구성됩니다.또는 구성을 반복하십시오.각 기계 $ M $ , 기계를 시뮬레이션하여 이러한 가능성 중 하나가 발생했음을 쉽게 관찰 할 수 있습니다.