Máquinas de Turing: Conceptos, Computación Universal y Tesis de Church-Turing

Question 1

En una máquina de Turing, un procedimiento de decisión se ejecuta como una

Accepted Answer

Función computable

Answer

Tabla de verdad

Answer

Autómata finito

Answer

Gramática regular

Question 2

¿Cuál de los siguientes NO es un tipo de máquina de Turing?

Accepted Answer

Recursiva

Answer

Determinista

Answer

No determinista

Answer

Con restricciones

Question 3

La tesis de Church-Turing afirma que:

Accepted Answer

Todas las funciones computables pueden ser calculadas por una máquina de Turing.

Answer

Las máquinas de Turing son más potentes que otros modelos de computación.

Answer

Los problemas no resolubles no pueden ser resueltos por ninguna máquina.

Answer

Las máquinas de Turing son equivalentes a los lenguajes regulares.

Question 4

¿Cuál de las siguientes afirmaciones sobre las máquinas de Turing universales es cierta?

Accepted Answer

Pueden simular cualquier otra máquina de Turing.

Answer

Son más eficientes que las máquinas de Turing ordinarias.

Answer

Pueden resolver cualquier problema computable en tiempo polinómico.

Answer

Requieren una cantidad infinita de cinta para funcionar.

Question 5

La máquina de Turing en la que los movimientos de la cinta están restringidos a una sola dirección se conoce como:

Accepted Answer

Máquina de Turing unidireccional

Answer

Máquina de Turing bidireccional

Answer

Máquina de Turing determinista

Answer

Máquina de Turing no determinista

Question 6

El problema de la parada para las máquinas de Turing se refiere a:

Accepted Answer

Determinar si una máquina de Turing se detendrá en una entrada determinada.

Answer

Encontrar la máquina de Turing más eficiente para un problema dado.

Answer

Probar la corrección de una máquina de Turing.

Answer

Simular una máquina de Turing en un ordenador.

Question 7

¿Cuál de los siguientes lenguajes NO es reconocible por una máquina de Turing?

Accepted Answer

{0101}

Answer

{0,1}

Answer

{a,b}*{a,b}{a,b}

Answer

{a,b}*

Question 8

Una Máquina de Turing, según su definición formal, consiste en:

Accepted Answer

Una cinta infinita, un cabezal de lectura/escritura y un conjunto finito de estados

Answer

Una placa base, un procesador y una memoria RAM

Answer

Una pantalla, un teclado y un ratón

Question 9

¿Cuál es el enunciado principal de la Tesis de Church-Turing?

Accepted Answer

Establece la equivalencia entre las Máquinas de Turing y los modelos de computación actuales

Answer

Demuestra que las Máquinas de Turing son más potentes que las computadoras electrónicas

Answer

Afirma que todas las Máquinas de Turing son equivalentes en capacidad de cálculo

Question 10

Una Máquina de Turing universal es aquella que:

Accepted Answer

Es capaz de simular el comportamiento de cualquier otra Máquina de Turing

Answer

Posee un número ilimitado de estados

Answer

Siempre alcanza una configuración final

Answer

Utiliza una cinta infinita en ambas direcciones

Question 11

¿Cuál de las siguientes afirmaciones describe una limitación de las Máquinas de Turing?

Accepted Answer

No pueden resolver problemas que requieran una cantidad exponencial de memoria

Answer

Sólo pueden procesar información en formato binario

Answer

Son demasiado lentas para aplicaciones prácticas

Question 12

Una configuración de una Máquina de Turing consta de:

Accepted Answer

El estado actual, la posición del cabezal de lectura/escritura y el contenido de la cinta

Answer

El nombre del archivo, el tamaño del disco y la versión del sistema operativo

Answer

La entrada del usuario, el programa y el estado de la memoria

Question 13

¿Cuál de las siguientes funciones NO es computable por una Máquina de Turing?

Accepted Answer

El problema de la detención

Answer

Buscar un elemento en una matriz

Answer

Realizar una suma de dos números

Answer

Ordenar una lista de números

Question 14

Una Máquina de Turing determinista se caracteriza por:

Accepted Answer

Tener una única transición posible para cada configuración

Answer

Poder cambiar de estado espontáneamente

Answer

Poder leer varias celdas de la cinta simultáneamente

Question 15

Proporciona un ejemplo de una tarea que no puede ser reconocida por una Máquina de Turing:

Accepted Answer

Comprender el lenguaje natural

Answer

Resolver ecuaciones algebraicas

Answer

Generar números aleatorios

Question 16

La complejidad computacional de una Máquina de Turing se mide principalmente en términos de:

Accepted Answer

Tiempo y espacio

Answer

Memoria y ancho de banda

Answer

Velocidad y precisión

Answer

Coste y rendimiento

Question 17

Las Máquinas de Turing son un modelo teórico de computación que puede simular:

Accepted Answer

Cualquier otro modelo de computación.

Answer

Exclusivamente problemas de lógica proposicional.

Answer

Un conjunto limitado de problemas computacionales.

Answer

Solo computaciones aritméticas básicas.

Question 18

La Tesis de Church-Turing afirma que:

Accepted Answer

Cualquier función computable por un algoritmo puede ser calculada por una Máquina de Turing.

Answer

Las Máquinas de Turing son más eficientes que otros modelos de computación.

Answer

Las Máquinas de Turing son el único modelo de computación posible.

Answer

Todos los problemas computacionales pueden ser resueltos por una Máquina de Turing.

Question 19

El estado de una Máquina de Turing en un momento dado se define por:

Accepted Answer

Su configuración de cinta y su estado interno.

Answer

La secuencia de instrucciones que ha ejecutado hasta ese momento.

Answer

Solo su estado interno.

Answer

Solo la posición del cabezal de lectura/escritura.

Question 20

Para una Máquina de Turing que utiliza el alfabeto {0, 1}, ¿cuál de las siguientes configuraciones de cinta es válida?

Accepted Answer

101001

Answer

10210

Answer

abcdefg

Answer

10-101

Question 21

¿Qué tipo de función NO puede ser calculada por una Máquina de Turing?

Accepted Answer

Una función no recursiva.

Answer

Una función exponencial.

Answer

Una función lineal.

Answer

Una función trigonométrica.

Question 22

¿Cuál de las siguientes es una operación válida que puede realizar una Máquina de Turing en su cinta?

Accepted Answer

Escribir un símbolo.

Answer

Copiar una sección de la cinta a otra ubicación.

Answer

Mover el cabezal 10 posiciones a la derecha.

Answer

Borrar toda la cinta.

Question 23

El Teorema de Rice determina si una propiedad arbitraria de las Máquinas de Turing es:

Accepted Answer

Decidible o no.

Answer

Recursiva o no recursiva.

Answer

Computable o no computable.

Answer

Compleja o simple.

Question 24

Las Máquinas de Turing Universales:

Accepted Answer

Pueden simular cualquier otra Máquina de Turing.

Answer

Tienen un número ilimitado de estados.

Answer

Son más rápidas que las Máquinas de Turing ordinarias.

Answer

Solo pueden aceptar lenguajes regulares.

Question 25

Un lenguaje recursivamente enumerable es un lenguaje que puede ser aceptado por:

Accepted Answer

Una Máquina de Turing que no siempre se detiene.

Answer

Una gramática libre de contexto.

Answer

Un autómata finito.

Answer

Una máquina de estados finitos determinista.

Question 26

En una Máquina de Turing, ¿qué símbolo se puede leer y escribir en cualquier posición de la cinta?

Accepted Answer

Símbolo de la cinta

Answer

Símbolo de transición

Answer

Símbolo inicial

Answer

Símbolo de detención

Question 27

La Tesis de Church-Turing establece que:

Accepted Answer

Cualquier función que pueda ser computada por un ordenador moderno también puede ser computada por una Máquina de Turing

Answer

Todas las Máquinas de Turing son ordenadores modernos

Question 28

Una Máquina de Turing que puede simular cualquier otra Máquina de Turing se conoce como:

Accepted Answer

Máquina de Turing universal

Answer

Máquina de Turing que resuelve cualquier problema

Answer

Máquina de Turing con infinitos estados

Question 29

¿Qué propiedad de las Máquinas de Turing las hace tan potentes?

Accepted Answer

Su capacidad de cambiar de estado y mover la cinta

Answer

Su interfaz de usuario intuitiva

Answer

Su tamaño y complejidad

Answer

Su velocidad de procesamiento

Question 30

¿Qué problema no pueden resolver las Máquinas de Turing?

Accepted Answer

El problema de la parada

Answer

El problema del viajante

Answer

El problema de la suma de subconjuntos

Answer

El problema de la mochila

Question 31

¿Cuál de las siguientes opciones NO es un componente de una Máquina de Turing?

Accepted Answer

Una pila de elementos

Answer

Un conjunto de estados

Answer

Una cinta infinita

Answer

Un cabezal de lectura/escritura

Question 32

La Tesis de Church-Turing postula que:

Accepted Answer

Cualquier función computable puede ser calculada por una Máquina de Turing.

Answer

Existe una jerarquía infinita de máquinas con capacidades de cómputo cada vez mayores.

Answer

Las Máquinas de Turing son las máquinas más potentes que se pueden construir.

Answer

Todas las funciones computables pueden ser calculadas en tiempo polinomial.

Question 33

Una Máquina de Turing acepta una entrada cuando:

Accepted Answer

El cabezal se encuentra en un estado de aceptación al finalizar la computación.

Answer

Se ha leído toda la entrada en la cinta.

Answer

Se ha realizado un número determinado de pasos.

Answer

La cinta está completamente vacía.

Question 34

¿Qué característica define a una Máquina de Turing determinista?

Accepted Answer

Para cada estado y símbolo de entrada, existe una única transición posible.

Answer

Puede volver a un estado anterior durante la computación.

Answer

Puede leer y escribir en la cinta simultáneamente.

Answer

Puede realizar múltiples operaciones en un solo paso.

Question 35

En relación a la capacidad de simulación, ¿puede una Máquina de Turing simular un Autómata Finito Determinista (AFD)?

Accepted Answer

Sí, un AFD puede ser simulado por una Máquina de Turing.

Answer

No, un AFD no puede ser simulado por una Máquina de Turing.

Answer

Solo si el AFD no tiene ciclos.

Answer

Solo si el AFD tiene un número finito de estados.

Question 36

El problema de la parada para una Máquina de Turing consiste en:

Accepted Answer

Determinar si una Máquina de Turing se detendrá o no para una entrada dada.

Answer

Simular una Máquina de Turing en otra Máquina de Turing.

Answer

Encontrar la Máquina de Turing más eficiente para un problema dado.

Answer

Determinar si una Máquina de Turing acepta un lenguaje regular.

Question 37

¿Cuál de las siguientes acciones NO puede realizar una Máquina de Turing en un solo paso?

Accepted Answer

Leer y escribir en la cinta simultáneamente.

Answer

Mover el cabezal a la izquierda o a la derecha.

Answer

Escribir un símbolo en la celda actual de la cinta.

Answer

Cambiar de estado.

Question 38

¿Cuál de los siguientes problemas puede ser resuelto por una Máquina de Turing?

Accepted Answer

Determinar si un número es primo.

Answer

Resolver el problema de la parada para cualquier Máquina de Turing.

Answer

Crear una obra de arte original.

Answer

Predecir el comportamiento del mercado de valores con total precisión.

Question 39

La complejidad temporal de una Máquina de Turing se refiere a:

Accepted Answer

El número de pasos que la Máquina de Turing necesita para completar una tarea.

Answer

El tamaño de la cinta utilizada por la Máquina de Turing.

Answer

El número de estados de la Máquina de Turing.

Answer

La cantidad de veces que la Máquina de Turing cambia de estado.

Question 40

Una Máquina de Turing universal se caracteriza por su capacidad de:

Accepted Answer

Simular cualquier otra Máquina de Turing.

Answer

Resolver cualquier problema computacional, incluyendo los indecidibles.

Answer

Aprender de la experiencia y mejorar su rendimiento.

Answer

Ser más eficiente que cualquier otra Máquina de Turing.