기억할 수있는 튜링 머신

Question

특수 튜링 머신은 표준 튜링 머신과 같이 정의되며, 각 단계는 왼쪽 가장자리에서부터 테이프의 헤드 위치로의 머리 위치로 각 단계만이 만들어집니다. (이 경우의 전환 기능은 Q x γ * -> Q x Γ x {L, R}에 속합니다)

다음 중 어느 것이 사실입니까?

a. 모든 언어 L은 L을 결정하는 특수 튜링 머신이있는 경우에만 L을 결정하는 튜링 머신이 있습니다.

b. 모든 언어 L은 다항식 (입력 길이 다항식)에서 L을 결정하는 특수 튜링 머신이있는 경우에만 다항식 시간이있는 경우에만 L을 결정하는 튜링 머신이 있습니다.

c. A, B 답변이 정확합니다.

d. A, B 답변이 잘못되었습니다.

와 내 질문은 다음과 같습니다. 정답은 D이고 왜 그런지 이해할 수 없습니다.

대답은 다음과 같습니다. 각 언어는 n은 입력 길이 인 경우 선형 입력 길이 시간 (o (n))에서 특수 튜링 머신으로 결정할 수 있습니다. 전환 기능은 공백 공간이 보이지 않는 한 오른쪽으로 이동하며, 테이프에 쓰여진 단어에 따라 빈 공간이 수신 또는 거부로 전환되는 것을 보는 것처럼 보인다.

내 질문은 : 단어를 거부하거나 수락할지 여부를 어떻게 결정할 수 있습니까? PDA, DFA와 같은 다른 계산 모델에서는 전이 기능을 유사하게 정의하고 모델에 전원이 추가되지 않았습니다. 왜 튜닝 머신에 관해서 전환 기능이 변경된 결과로 전원이 계산 모델에 추가되는 것처럼 보이는 이유는 무엇입니까?

감사합니다.

Answer 1

언어 $ l $ 특수 튜링 머신 $ T $ 이 $ L $ 다항식 시간.

튜링 머신은 3 가지 상태를 가지고 있습니다 : 초기 상태 $ Q_0 $ , 수락 상태 $ Q_A $ 및 거부 상태 $ Q_R $ . $ \ gamma $ 빈 기호 $ \ varepsilon $ 를 포함하여 테이프 알파벳으로 보내십시오. $ \ alpha x $ 은 왼쪽 가장자리에서 테이프의 머리 위치로 시작하는 테이프의 내용을 나타냅니다. 여기서 $ \ alpha \ in \ in \ in \ in \ in \ span> 및 $ x \ in \ gamma $ . 평소와 같이, 나는 입력이 테이프의 시작부터 시작하여 머리가 처음에 테이프의 시작 부분에 위치한다고 가정 할 것입니다. 전이 함수 $ \ delta $ 은 다음과 같이 정의됩니다.

• $ \ △ X (Q_0, \ alpha x)= (Q_0, x, r) $ $ x \ neq \ vaepsilon $
• $ \ Δ (Q_0, \ alpha x)= (Q_A, x, r) $ $ x=vaepsilon $ 및 $ \ alpha \ l $
• $ \ Δ (Q_0, \ alpha x)= (Q_A, x, r) $ $ x=vaepsilon $ 및 $ \ alpha \n$

정규 튜링 머신에 대한 미확인 언어가 있기 때문에, 이는 A와 B가 거짓임을 즉시 의미합니다.

answers d와 c는 불분명합니다. 그들은 "두 답변"에 대해 이야기하지만 $ 4 $ 가능한 답변이 주어집니다.