Cuál de las
siguientes afirmaciones es cierta:
Una máquina de Turing cuyo estado inicial coincida
con el estado de parada acepta toda cadena
De las
siguientes características marque dos de las que corresponden con la cinta de
una Máquina de Turing
Puede contener un caracter por celda
Se puede escribir en ella
De las
siguientes afirmaciones una de ellas es FALSA:
Una máquina de Turing que siempre mueve su cabeza a
la izquierda se diferencia de un autómata finito principalmente en que tiene
poder de escribir en su cinta, y por tanto almacenar datos a modo de un
autómata de pila y reconocer lenguajes independientes del contexto.
Indique cuál
de las siguientes afirmaciones es verdadera:
Es posible diseñar una máquina de Turing de tres
cintas que reconozca tres lenguajes.
Seleccione
cuál de las siguientes situaciones no es posible cuando una máquina de Turing
determinista examina una cadena:
La máquina abandona los cálculos por no encontrar
ninguna transición aplicable
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:
La máquina podría devolver el resultado en notación
decimal
La
afirmación: “Una máquina de Turing universal es capaz de decidir cualquier
lenguaje independiente del contexto.”
Es verdadera
Una de las
siguientes afirmaciones es verdadera selecciónela:
La tesis de Turing no implica que los lenguajes más
generales que existan sean los lenguajes estructurados por frases.
El
desplazamiento de la cabeza de una Máquina de Turing, se realiza en un solo
sentido, y no hacia ambos lados
Falso
Es posible
volver a un estado, por el que previamente ya había pasado
Verdadero