¿Qué es la computabilidad?
La teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que se pueden resolver con un algoritmo o equivalentemente con una máquina de Turing.
¿Qué estudia la complejidad de un algoritmo?
La complejidad algorítmica representa la cantidad de recursos (temporales) que necesita un algoritmo para resolver un problema y por tanto permite determinar la eficiencia de dicho algoritmo.
¿Qué es el teorema de Turing?
Alan Turing demostró en su famoso teorema de indecibilidad que no es posible escribir un programa de ordenador que nos diga si otro programa cualquiera se queda o no se queda colgado. Este es el famoso «problema de la parada» para el que no hay programa posible.
¿Qué es un problema computable?
Se le llama problema computable a aquella abstracción de la realidad que tiene representación algorítmica. Los algoritmos permiten encontrar la solución a problemas computables. En realidad todo el tiempo estamos aplicando algoritmos para resolver problemas.
¿Qué es la teoría de la computabilidad?
6 ¿Qué otros formalismos equivalen a las máquinas de Turing? 7 ¿Qué problemas requieren máquinas más poderosas? La Teoría de la Computabilidad es el estudio matemático de los modelos de computación. Como tal estudio teórico, se originó en la década de los años 30 con los trabajos de los lógicos Church, Gödel, Kleene, Post y Turing.
¿Qué es un número computable?
Turing demostró que se trata de un problema indecidible. Un número computable es un número real que puede ser aproximado por un algoritmo con un nivel de exactitud arbitrario. Turing demostró que casi todos los números no son computables. Por ejemplo, la Constante de Chaitin no es computable aunque sí que está bien definida.
¿Qué es un problema indecidible?
Un problema indecidible es uno que no puede ser resuelto con un algoritmo aun si se dispone de espacio y tiempo ilimitado. Actualmente se conocen muchos problemas indecidibles, como por ejemplo:
¿Quiénes fueron los autores de la teoria de la incompletitud?
Church (1936p, 1936f) y Turing (1936), inspirados por las técnicas usadas por Gödel (1931) para probar sus teoremas sobre la incompletitud, demostraron por separado que no es posible decidir el Entscheidungsproblem de una manera eficaz.
