Cuál de las siguientes afirmaciones es cierta:
a. Es posible que un lenguaje sea estructurado por
frases pero no exista ninguna máquina de Turing que se detenga exclusivamente
cuando las cadenas escritas en su cinta pertenezcan al lenguaje
b. Una
máquina de Turing cuyo estado inicial coincida con el estado de parada acepta
toda cadena
c. Ninguna de las anteriores
d. Cualquier lenguaje puede ser reconocido por una
máquina de Turing
Indique cuál de las tres siguientes afirmaciones es
cierta (en caso de que las tres lo sean, señale la opción d):
a. Con una
máquina de Turing ordinaria (cuya cinta es infinita en una sola dirección) es
posible simular una máquina de Turing infinita en ambas direcciones
b. Es posible establecer una aplicación biunívoca
(relación uno a uno) entre las máquinas de Turing deterministas y los lenguajes
estructurados por frases de modo que a cada máquina le corresponda el lenguaje
que acepta
c. Una máquina de Turing que tenga uno o más
estados de parada siempre concluye sus cálculos
d. Las tres afirmaciones son ciertas
La cinta de una Máuina de Turing es infinita hacia:
a. Arriba
b. Abajo
c. La Izquierda
d. La
Derecha
La operación de la máquina de turing consta de los
siguientes pasos: (Seleccione más de una respuesta)
a. Escribir el resultado de la máquina de turing
b. Lee un
carácter en la cinta
c. Realiza
una acción en la cinta
d. Efectúa
una transición de estado
Escoger cuál de las siguientes afirmaciones es
falsa:
a. Todo conjunto finito de cadenas es un lenguaje
regular
b. Mediante autómatas de pila de 2 pilas podría
reconocerse un mayor número de lenguajes que mediante los usuales autómatas de
una sola pila. En cada transición, el autómata podría almacenar y leer datos de
dos pilas distintas.
c. Si L es un
lenguaje aceptable por máquinas de Turing, también lo es el lenguaje
complementario de L
La máquina de Turíng opera cíclicamente dado que:
a. Una instrucción viene representada por una
quíntupla.
b. La cabeza puede leer y escribir en un mismo
carácter.
c. Comienza por una palabra de entrada.
d. Al
comienzo de un ciclo se parte de una determinada configuración.
No hay diferencia alguna entre una Máquina de
Turing y una Máquina Universal de Turing PORQUE Las dos hacen referencia a la
misma máquina
a. La Afirmación es FALSA, pero la Razón es una
proposición VERDADERA
b. La Afirmación es VERDADERA, pero la Razón es una
proposición FALSA
c. La Afirmación y la Razón son VERDADERAS pero la
Razón NO es una explicación CORRECTA de la Afirmación
d. La Afirmación
y la Razón son VERDADERAS y la Razón es una explicación CORRECTA de la
Afirmación
La afirmación: “Una máquina de Turing universal es
capaz de decidir cualquier lenguaje independiente del contexto.”
a. Es falsa
b. Sólo es verdadera para lenguajes independientes
del contexto reconocibles mediante autómatas de pila deterministas
c. Es
verdadera
Para las siguientes afirmaciones Indique cuál es
verdadera:
a. Un autómata de pila determinista nunca puede
meterse en un ciclo que se ejecute indefinidamente
b. Una
máquina de Turing determinista puede meterse en un ciclo que se ejecute
indefinidamente.
c. Un autómata finito nunca puede meterse en un
ciclo que se ejecute indefinidamente
Una de las siguientes afirmaciones es verdadera
selecciónela:
a. La tesis
de Turing no implica que los lenguajes más generales que existan sean los lenguajes
estructurados por frases.
b. Dada una máquina de Turing, existe una gramática
estructurada por frases que genera el mismo lenguaje que acepta el autómata si
y sólo si la máquina es determinista.
c. La tesis de Turing implica que para todo
lenguaje existe una máquina de Turing que lo acepta, ya sea el alfabeto finito
o infinito.
Suponga que se desea construir una máquina de
Turing que enumere en orden sobre su cinta todos los números enteros. Indique
cuál de las siguientes afirmaciones es verdadera:
a. La máquina necesariamente habría de proporcionar
el resultado en notación binaria
b. La
máquina podría devolver el resultado en notación decimal
c. No existe ninguna máquina de Turing, ya que el
problema planteado no es computable
Indique cuál de las siguientes afirmaciones es
verdadera:
a. Es
posible diseñar una máquina de Turing de tres cintas que reconozca tres
lenguajes.
b. Con una única máquina de Turing, ya sea de una o
varias cintas, determinista o no determinista, sólo es posible reconocer un
lenguaje
c. Con una única máquina de Turing pueden
reconocerse tres lenguajes: el lenguaje de las cadenas que acepta, el lenguaje
de las cadenas que rechaza y el lenguaje de las cadenas que llevan a la máquina
a un bucle de ejecución infinita.
En una Máquina de Turing la cabeza lectora es de
Escritura y Lectura debido a que:
a. La cabeza se mueve Unidireccionalmente.
b. La cinta
puede ser modificada en curso de ejecución.
c. Se lee un Carácter en la Cinta.
d. No pasa repetidas veces sobre un mismo segmento.
La máquina universal de Turing esta diseña para
realizar cualquier cálculo específico – particular debido a que:
a. Es un intérprete de la información de salida
b. Es capaz
de realizar cualquier algoritmo
c. Parará cuando el cálculo sea indeterminado.
d. Las instrucciones se basan en una fase del
algoritmo universal.
Corresponden con acciones sobre una cinta en la
Máquina de Turing que son excluyentes (si se realiza una no se realiza la otra)
a. Mover la
cabeza a la Izquierda o a la Derecha
b. Escribir una Palabra en la Memoria
c. Escribir
un carácter en la cinta
d. Recuperar el último carácter leído
Calificación 23,3/25
Calificación 23,3/25