Las compus

L a formalización del concepto de computabilidad
El algoritmo es un conjunto de instrucciones efectivo y explícito que permita hallar la solución de un problema. Cuando hablamos deproblemas nos referimos a problemas abstractos o generales, tales como usar dos números.
Un problema abstracto es resoluble algorítmicamente si es posible construir un algoritmo que resuelva cadaproblema concreto de la clase. Los problemas abstractos se clasifican en decidibles e indecidibles.
En 1920 los matemáticos dedican esfuerzos a entender la noción de función. Una funciónes un conjunto ordenado de pares con dominio y rango, pero no describe el comportamiento de la función. Alonzo Church crea la teoría -cálculo en las que las funciones son consideradasreglas, establece las propiedades teóricas básicas de este formalismo. Conceptos como variable, sustitución, ocurrencias libres y ligadas de una variable es una sola expresión y renombramiento.La idea clave subyacente en el -calculo es esencial abstracta: de hecho, la clave del mismo es una operación matemática que el propio Church llama abstracción. Stephen Kleene comprobó quetodas las funciones numéricas que podía -definibles, definibles usando el -calculo.
En 1936 Church demostró que ninguna función recursiva pudiera decidir la validez de formulas del primerorden demostrando, en consecuencia la inexistencia de algoritmos para decidir la validez de las formulas de la lógica de primer orden.
Alan Turing propuso un nuevo modelo de calculabilidad:sus maquinas abstractas actualmente llamadas maquinas de Turing, con la cual le permitió introducir la noción de función computable con una maquina abstracta.
En la práctica, no solo setrabaja con la equivalencia de estas condiciones, sino que se conjetura que cualquier noción de calculabilidad que se pueda construir será equivalente a cualquiera de las anteriores.