Diferencia entre revisiones de «Teoría de la computabilidad»
Contenido eliminado Contenido añadido
m Revertidos los cambios de 201.170.109.42 a la última edición de Irbian |
|||
Línea 18:
Pero fueron otros los que mediante una serie de investigaciones mostraron que esto no era posible. En contra de esta idea K. Gödel sacó a la luz su conocido [[Teoremas de la incompletitud de Gödel|Primer Teorema de Incompletitud]]. Este viene a expresar que todo sistema de primer orden consistente que contenga los [[Teorema|teoremas]] de la [[aritmética]] y cuyo conjunto de [[axioma]]s sea [[Recursión|recursivo]] no es completo. Gödel construyó una fórmula que es satisfactoria pero que no puede ser probada en el sistema. Como consecuencia, no es posible encontrar el sistema formal deseado por Hilbert en el marco de la [[lógica de primer orden]], a no ser que se tome un conjunto no recursivo de axiomas.
Una posterior versión, que resulta más general, del teorema de incompletitud de Gödel, indica que ningún sistema deductivo que contenga los teoremas de la aritmética, y con los axiomas recursivamente enumerables puede ser [[Consistencia lógica|consistente]] y [[completud|completo]] a la vez. Esto hace pensar, a nivel intuitivo, que no va a ser posible definir un sistema formal.
==¿Qué problemas puede resolver una máquina de Turing? ==
| |||