Programa

Instituto Tecnológico de Hermosillo

INGENIERÍA EN SISTEMAS COMPUTACIONALES.

Teoria De La Computacion

Unidad 5.- Decibilidad

Hermosillo, Sonora, junio de 2011

Introducción
1.- ¿Enqué consiste la decibilidad de Teorías lógicas?
Consiste en algún método que determine si un objeto pertenece a un conjunto

2.- ¿En teoría de la computación, a que se refiere con el concepto dedecibilidad ?
Se refiere a los problemas que se pueden resolver mediante un algoritmo

3.- ¿En qué consiste la teoría de la complejidad?
Se basa en la cantidad de tiempo, espacio u otro recurso quese necesita para reconocer a un lenguaje en algún dispositivo de cómputo universal como la máquina de turing

4.-explica ampliamente en qué consiste el primer teorema de recursión
Primer teorema deRecursión. Todo operador entre funciones calculables que sea recursivo (esto es que se defina la imagen de f mediante una función calculable en términos de una parte finita de f), tiene una funciónparcial computable que es el menor punto fijo, es decir, esta función es un punto fijo y cualquier otro punto fijo del operador es una extensión de esa función.
5.- ¿Qué son los lenguajes decidibles?Al igual que con los demás autómatas, la colección de cadenas aceptadas por una maquina de Turing ‘M’ se llama Lenguaje aceptado por la maquina (lenguaje decidible) y se representa con L(M). se diceque un lenguaje L es un lenguaje decidible si existe una maquina de Turing ‘M’ tal que L=L(M)

6.- ¿Cuál es el objetivo de la teoría de la computabilidad?
El objetivo es identificar las funcionesque pueden calcularse con al menos un sistema computacional. En otras palabras para decir si una función puede calcularse por algún algoritmo

7.-¿ cuáles son los recursos requeridos en la teoríade la complejidad computacional?
Tiempo y espacio de almacenamiento

8.-¿En que difiere la teoría de la complejidad computacional respecto a la teoría de la computabilidad?
La teoría de la...