Decidibilidad

CUESTIONARIO Unidad 5. – DECIBILIDAD
1. ¿En qué consiste la decibilidad de Teorías Lógicas?
Si el conjunto de teoremas visto como un lenguaje es reconocido por una máquina de Turing, entonces lateoría lógica es decidible. Y viceversa.

2. ¿En Teoría de la Computación, a que se refiere con el concepto de “decibilidad”?
Si existe un método efectivo para comprobar que un objeto pertenece a unafórmula o conjunto de fórmulas.
3. ¿En qué consiste la Teoría de la Complejidad?
Estudia cuantos recursos necesita un algoritmo decidible para ejecutar (recursos de tiempo, espacio, número deprocesadores, tipo de máquina, etc.).
4. Explicar ampliamente en que consiste el primer Teorema de Recursión
Todo operador entre funciones calculables que sea recursivo (esto es que se define la imagende f mediante una función calculable en términos de una parte finita de f), tiene una función parcial computable que es el menor punto fijo, es decir, esta función es un punto fijo y cualquier otropunto fijo del operador es una extensión de esa función.
5. Que son los lenguajes decidibles?
Es aquel lenguaje L para el cual existe una máquina de Turing que puede aceptar cualquier cadena w∈L yrechazar cualquier cadena w∉L.
6. ¿Cuál es el objetivo de la Teoría de la Computabilidad?
Se estudia cuales lenguajes son decidibles con diferentes tipos de máquinas.
7. ¿Cuáles son los recursosrequeridos en la teoría de la complejidad computacional?
Tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema).
Espacio (mediante unaaproximación a la cantidad de memoria utilizada para resolver un problema).
Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema enparalelo.
8. ¿En que difiere la Teoría de la Complejidad Computacional respecto a la Teoría de la Computabilidad?
En que ésta se ocupa de la factibilidad de expresar problemas como algoritmos...