Segundo Examen Parcial de Teoría de la Computabilidad
Authored by Idelia Jarquín
Other
University
Used 1+ times
AI Actions
Add similar questions
Adjust reading levels
Convert to real-world scenario
Translate activity
More...
Content View
Student View
14 questions
Show all answers
1.
MULTIPLE SELECT QUESTION
45 sec • 5 pts
Las técnicas para la construcción de máquinas de Turing:
Pistas múltiples
Señalamiento de símbolos.
Corrimiento y subrutinas.
Ninguna de las anteriores es correcta.
2.
MULTIPLE SELECT QUESTION
45 sec • 5 pts
¿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.
3.
MULTIPLE SELECT QUESTION
45 sec • 5 pts
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
4.
MULTIPLE SELECT QUESTION
45 sec • 5 pts
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.
5.
MULTIPLE CHOICE QUESTION
30 sec • 5 pts
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
6.
FILL IN THE BLANKS QUESTION
1 min • 5 pts
¿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"?
.
(a)
7.
MULTIPLE CHOICE QUESTION
30 sec • 5 pts
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
Access all questions and much more by creating a free account
Create resources
Host any resource
Get auto-graded reports
Continue with Google
Continue with Email
Continue with Classlink
Continue with Clever
or continue with
Microsoft
%20(1).png)
Apple
Others
Already have an account?
