Segundo Examen Parcial de Teoría de la Computabilidad

Las técnicas para la construcción de máquinas de Turing:

• Almacenamiento en el control finito
• Pistas múltiples

• Señalamiento de símbolos.

• Corrimiento y subrutinas.

• Ninguna de las anteriores es correcta.

¿Cuáles son las características para la construcción de Máquina de Turing?.

• La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.

• .Las operaciones que se pueden realizar en esta máquina se limitan a: Avanzar el cabezal lector/escritor hacia la derecha Visualización de una Máquina de Turing, en la que se ve el cabezal y la cinta que se lee. Avanzar el cabezal lector/escritor hacia la izquierda.

• La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribir dos nuevos valores.

• Las tareas que se pueden realizar en esta máquina se limitan a: Avanzar el cabezal lector/escritor hacia la izquierda. Visualización de una Máquina de Turing, en la que se ve el cabezal y la cinta que se lee. Avanzar el cabezal lector/escritor hacia el centro.

Lenguajes aceptan las Máquinas de Turing:

• se dice que es recursivamente enumerable, si es aceptado por alguna máquina de Turing.

• Es decir, L es recursivamente enumerable si para alguna MT M tenemos que: L(M)={w Î ||* | qwL* upv para p Î F y U, V, V Î || }

• (donde q es el estado inicial de M y F es el conjunto de estados finales de M).

• Un lenguaje L es recursivo si L es recursivamente enumerable y hay alguna MT que para sobre todas las entradas que acepta L

La diferencia existe entre lenguaje decidible y lenguajes aceptados es:

• Lenguaje decidible:  Es aquel lenguaje L para el cual existe una MT que puede aceptar cualquier cadena w Î L y rechazar cualquier cadena w pertenece a L.

• Lenguajes aceptables: Es aquel lenguaje L para el cual no existe ninguna Máquina de Turing que puede aceptar cualquier cadena w pertenece a L y rechazar cualquier cadena w no pertenece a L.

• Lenguaje decidible:  Es aquel lenguaje L para el cual existe una MT que puede no puede aceptar cualquier cadena w Î L y rechazar cualquier cadena w pertenece a L.

• Lenguajes aceptables: Es aquel lenguaje L para el cual existe alguna Máquina de Turing que puede aceptar cualquier cadena w pertenece a L y rechazar cualquier cadena w no pertenece a L.

Un sistema formal es decidible cuando: Existe un algoritmo que diga en tiempo finito si una cadena cualquiera es un teorema o no lo es.

• Verdadero

• Falso

¿Cuál es el nombre de este procedimiento: "Las computaciones terminales en una máquina de Turing dada, pueden “realizarse” como la intersección de dos lenguajes libres de contexto. En otras palabras, el proceso de “correr una máquina de Turing sobre una entrada dada” puede realizarse por dos autómatas de pila ``corriendo en paralelo''. Sea M=(Q, A, t, q0, F) una máquina de Turing. Sea DI una computación, terminal o intermedia"?

.

Las funciones computables son: El objeto básico de estudio de la teoría de la computabilidad y consisten en las funciones que pueden ser calculadas por una máquina de Turing.

• Verdadero

• Falso

¿Quién fue el creador de las máquinas de Turing?

• Steve Jobs

• Bill Gates

• Alan Turing

• Thomas Edison

¿Cuál es el concepto central de las máquinas de Turing?

• Capacidad de volar sin alas

• Habilidad para predecir el futuro

• Capacidad de cocinar cualquier receta

• Capacidad de simular cualquier algoritmo de cálculo

¿Qué son los problemas indecidibles en el contexto de las máquinas de Turing?

• Problemas que son fáciles de resolver para una máquina de Turing

• Problemas que pueden ser resueltos por una máquina de Turing

• Problemas que no pueden ser resueltos por una máquina de Turing

• Problemas que no existen en el contexto de las máquinas de Turing