이 PDF 에서 아래 문제를 발견했습니다.
M이 빈 테이프에서 시작될 때 공백이 아닌 기호를 기록하는지 여부에 관계없이 TM M이 주어졌습니다.
주어진 솔루션은 다음과 같습니다.
머신이 공백으로 만 쓰도록합니다. 상징. 그러면 w에 대한 com 계산의 구성 수는 q × 2이며, 여기서 q는 M의 상태 수입니다. 요소 2는 선택을위한 것입니다. 머리 움직임의 방향; 쓰여진 기호는 항상 비어 있기 때문에 요소가 없습니다. 따라서 문제는 다음 기계에 의해 결정될 수 있습니다. 입력 (M, w), q x 2 단계에 대해 w에서 M 실행; M이 공백이 아닌 기호를 쓰면 yes 대답으로 중지하십시오. M이 공백이 아닌 기호를 작성하지 않으면 대답없이 중지합니다.
의심 :
Q1. 모든 qx 2 구성이 발생하는지 확인하는 방법 w에서 qx 2 단계를 실행하는 동안? 일부 구성은 qx 2 단계로 반복 될 수 있습니다.
Q2. 질문에 “시작할 때 빈 테이프 “, 대답은 비어 있지 않은 문자열 w에서 TM을 시뮬레이션하려고했습니다. 어떻게 말이 되나요?
답변
Q1 : 상태는 반복 될 수 있습니다. 요점은 상태가 반복되고 비어 있지 않은 기호가 작성되지 않은 경우 튜링 머신이 지금까지 발생한 일부 상태를 순환하는 데 필연적으로 멈춰 있기 때문에 절대 중단되지 않는다는 것을 알고 있습니다. 주기의 어떤 상태로 인해 TM이 공백이 아닌 기호를 작성하지 않았으므로 TM은 공백이 아닌 기호를 작성하지 않습니다.
$ 2q 이후 $ 단계, 비어 있지 않은 기호가 작성되었으며 “예”라고 대답 할 수 있습니다. 또는 모든 작성된 기호가 비어 있고 (적어도) 하나의 상태가 두 번 이상 발생 했어야합니다. 즉, “아니오”라고 대답 할 수 있습니다.
Q2 : 제 생각에는 $ w $ 는 빈 문자열로 정의됩니다. TM을 임의의 문자열 $ w $ 으로 시작할 수있는 경우 위 솔루션의 변형이 여전히 작동합니다. TM의 헤드가 $ w $ 의 시작 부분에서 시작한다고 가정합니다. 상태의 수는 테이프의 가능한 모든 상태를 고려하기 위해 최대 $ 1+ | w | $ 만큼 증가합니다 (빈 기호 만 기록 된 경우 이면 테이프에는 항상 $ w $ 의 $ 1+ | w | $ 접미사 중 하나가 포함됩니다. 헤드가 어디서나 시작할 수 있다면이 요소는 최대 $ 1+ | w | ^ 2 $ 입니다.
댓글
- 1 분기 " 공백이 아닌 기호가 작성되었으며 예 …라고 대답 할 수 있으며 아니요
라고 대답 할 수 있음을 의미합니까? b> "? 질문은 " M이 공백이 아닌 기호를 작성하는지 여부를 " 묻기 때문입니다. 2 분기 " 빈 기호로 덮어 쓴 w 위치의 하위 집합 수에 해당하는 상태 수를 얻지 못했습니다. "