어떤 입력 문자열을 지나서 머리를 움직이지 않아야하는 튜링 머신의 디지털 가능성

Question

$ L_1={\ LANGLE M, W rangle : m \ text {\ \ rangle은 입력 문자열을 지나서 머리를 움직이지 않는 TM입니다 \ \ span>



$ L_2={\ LANGLE M \ rangle : m \ text {모든 입력 문자열을 지나서 머리를 움직이지 않는 TM} \} $

위의 두 언어를 고려하십시오.나는 어떤 것들을 알고 싶은지 알고 싶다.

$ L_1 $ 은 $ m $ 이유로입력 문자열 $ W $ 의 가능한 구성으로 조합 수를지나 결정하고 결정하기 위해 튜링 머신 (TM)을 만들 수 있습니다.

그러나 $ l_2 $ 을 수행 할 수 있습니까?나는 $ l_2 $ 은 가능한 구성에 제한이 없을 수 없기 때문에 삭제가 불가능합니다.

Answer 1

$ \ mathsf {halt} $ \ span> $ \ overline {l_2} $ .

TM $ T $ 및 입력 $ W $ 을 작성하십시오. 새로운 TM $ n $ 길이 $ n $ , $를 시뮬레이트합니다. T $ $ W $ $ n $ 단계를 수행 한 다음이면 $ T $ $ n $ 단계, $ N $ 은 머리를 영원히 오른쪽으로 움직일 것입니다.

위의 감소에 갭이 있습니다. $ n $ 은 $ T $ 을 $ W $ $ n $ 단계, 왼쪽으로 움직일 때 입력에서 벗어날 수 있습니다 (입력은 원점의 오른쪽에 있음을 가정합니다. $ N $ 의 머리의 초기 위치 (삽입). 이 격차는 "테이프 번역"의 고전적인 트릭으로 해결할 수 있습니다. 시뮬레이션이 원점의 왼쪽으로 이동하는 경우 $ N $ 테이프의 전류를 오른쪽으로 번역하십시오. 그런 다음 $ N $ 은 기원의 왼쪽에있는 셀 인 것처럼 원점으로 간다. 이런 식으로 $ n $ 이 시뮬레이션 된 $ t $ $ w $ 이 중단되지 않습니다. ( $ N $ 을 사용하려면 원래를 인식하려면 원래 기호를 알려주는 "복합"기호로 원산지를 표시해야합니다. 예를 들어, 원래 기호는 $ a $ , $ n $ 은 $ a_o $ , $ a $ 이 아니지만 $ a $ . "화합물"기호는 $ n $ 이 테이프의 내용을 변환 할 때도 사용됩니다.)

$ \ mathsf {halt} $} $ 은 $ \ overline {l_2} $ 알지 못한다. 따라서 $ l_2 $ 은 아직되지 않습니다.