Máquina de Turing que puede recordar.

Question

La máquina de Turing especial se define igual que la máquina de Turing estándar, solo que cada paso se realiza de acuerdo con el contenido de la cinta que comienza desde el borde izquierdo a la posición de la cabeza en la cinta. (La función de transición en este caso pertenece a q x γ * -> q x γ x {l, r})

¿Cuál de los siguientes es cierto:

a. Cada idioma l tiene una máquina de Turing que decide L, si y solo si hay una máquina de Turing especial que decide l.

b. Cada idioma l tiene una máquina de Turing que decide l en un tiempo polinomial si y solo si hay una máquina de Turing especial que decide l en un polinomio (polinomial de longitud de entrada).

c. A, B respuestas son correctas.

d. A, B respuestas son incorrectas.

y mi pregunta es: La respuesta correcta es D y no puedo entender por qué.

La respuesta es: Cada idioma puede ser decidido por una máquina de Turing especial en tiempo de longitud de entrada lineal (O (N) cuando N es la longitud de entrada). Una función de transición va a la derecha siempre que no se vea un espacio en blanco, y tan pronto como vea un espacio en blanco, cambia a recibir o rechazar de acuerdo con la palabra escrita en la cinta.

Mi pregunta es: ¿Cómo puedo decidir si rechazar o aceptar una palabra? En otros modelos computacionales, como PDA, DFA, definimos la función de transición de manera similar, y no se agregó energía al modelo. ¿Por qué parece que se agrega ese poder al modelo computacional como resultado del cambio de la función de transición cuando se trata de máquinas de Turing?

gracias.

Answer 1

Dado cualquier idioma $ l $ Hay una máquina de Turing especial $ t $ que decide $ l $ en tiempo polinomial.

La máquina de Turing tiene 3 estados: los estados iniciales $ q_0 $ , el estado de aceptación $ q_a $ y el estado de rechazo $ q_r $ . Deje que $ \ gamma $ sea el alfabeto de la cinta (incluido el símbolo en blanco $ \ varepsilon $ ), y deja $ \ alfa x $ denota el contenido de la cinta que comienza desde el borde izquierdo a la posición de la cabeza en cinta, donde $ \ alfa \ in \ gamma ^ * $ y $ x \ in \ gamma $ . Como de costumbre, asumo que la entrada está escrita a partir del comienzo de la cinta y que la cabeza se coloca inicialmente al comienzo de la cinta. La función de transición $ \ delta $ se define de la siguiente manera:

• $ \ delta (q_0, \ alfa x)= (q_0, x, r) $ si $ x \ neq \ varepsilon $
• $ \ delta (q_0, \ alfa x)= (q_a, x, r) $ si $ x=varepsilon $ y $ \ alfa \ en l $
• $ \ delta (q_0, \ alfa x)= (q_a, x, r) $ si $ x=varepsilon $ y $ \ alfa \ no \ in l $

Dado que hay lenguajes indecibles para las máquinas de Turing regulares, esto implica inmediatamente que A y B son falsos.

Las respuestas D y C no están claras. Hablan de "ambas respuestas", sino que le dan $ 4 $ Posibles respuestas.