Máquina de Turing que pode lembrar

Question

Máquina de Turing Especial é definida como a máquina padrão de Turing, apenas que cada etapa é feita de acordo com o conteúdo da fita a partir da borda esquerda para a posição da cabeça na fita. (A função de transição nesse caso pertence a Q X γ * -> Q X γ X {L, R})

Qual das alternativas a seguir é verdadeira:

a. Cada idioma l tem uma máquina de Turing que decide l se e somente se houver uma máquina de Turing especial que decide l.

b. Cada idioma l tem uma máquina de Turing que decide l em um tempo polinomial se e somente se houver uma máquina de Turing especial que decide l em um polinomial (polinomial de comprimento de entrada).

c. A, b respostas estão corretas.

d. A, b respostas estão incorretas.

e minha pergunta é: A resposta correta é d e não consigo entender por quê.

A resposta é: Cada língua pode ser decidida por uma máquina de Turing especial em tempo de comprimento de entrada linear (O (n) quando n é o comprimento de entrada). Uma função de transição vai para a direita, desde que nenhum espaço em branco seja visto, e assim que você vê um espaço em branco para receber ou rejeitar de acordo com a palavra escrita na fita.

minha pergunta é: Como posso decidir se rejeitar ou aceitar uma palavra? Em outros modelos computacionais, como PDA, DFA, definimos a função de transição similarmente, e nenhuma potência foi adicionada ao modelo. Por que parece que o poder é adicionado ao modelo computacional como resultado da mudança da função de transição quando se trata de máquinas de Turing?

obrigado.

Answer 1

Dado qualquer linguagem $ l $ Há uma máquina de Turing especial $ t $ que decide $ l $ no tempo polinomial.

A máquina de Turing tem 3 estados: os estados iniciais $ q_0 $ , o estado de aceitação $ Q_A $ e o estado de rejeição $ q_r $ . Deixe $ \ gamma $ Seja o alfabeto de fita (incluindo o símbolo em branco $ \ VAREPSILON $ ), e deixe $ \ alfa x $ denotam o conteúdo da fita a partir da borda esquerda para a posição da cabeça na fita, onde $ \ alfa \ in \ gamma ^ * $ e $ x \ in \ gamma $ . Como de costume, vou assumir que a entrada é escrita a partir do começo da fita e que a cabeça é inicialmente posicionada no início da fita. A função de transição $ \ delta $ é definido da seguinte forma:

• $ \ delta (q_0, \ alpha x)= (q_0, x, r) $ se $ x \ NEQ \ VAREPSILON $
• $ \ delta (q_0, \ alpha x)= (q_a, x, r) $ se $ x=VAREPSILON $ e $ \ alfa \ em l $
• $ \ delta (q_0, \ alpha x)= (q_a, x, r) $ se $ x=varepsilon $ e $ \ alfa \ não \ in l $

Como existem idiomas indecidentes para máquinas de Turing Regular, isso implica imediatamente que A e B são falsos.

Respostas D e C não são claras. Eles falam sobre "ambas as respostas", mas você recebe $ 4 $ possíveis respostas.