Motivación ¿Existe algún problema que no pueda resolverse? ¿Puede cualquier lenguaje de programación resolver cualquier problema? ¿Qué necesita un lenguaje de programación para resolver cualquier problema algorítmico?
Motivación Computable o calculable: una función puede calcularse por algún algoritmo (más que por un algoritmo determinado). Funciones iniciales: Conjunto de funciones que son tan sencillas que no hay duda acerca de su computabilidad. Existen combinadores de funciones para los cuales está demostrado que se preserva la computabilidad.
Motivación Determinar funciones computables a partir de la combinación de funciones iniciales. Un lenguaje de programación que abarque todas las funciones iniciales tiene todo el poder computacional de las funciones recursivas primitivas. ¿Cuáles son las funciones iniciales y primitivas?
Funciones parciales Cualquier dato puede ser codificado como una cadena de ceros y unos (y en consecuencia como enteros no negativos). Funciones totales vs. Funciones parciales Ejemplos Función total de NxN: + Función parcial de NxN: div
Funciones parciales Todas las funciones computables son funciones parciales de la forma: Donde m y n son enteros no negativos
Funciones Iniciales Función cero: Función sucesor: Proyecciones: EJERCICIO: ¿Cuál es el resultado de la siguiente llamada a función?.
Funciones Iniciales Combinación: Composición: Ejercicios:
Funciones Iniciales Recursividad primitiva: suma 0 x = 0 suma (y + 1) x = 1 + (suma y x) Ejercicios: Definir las funciones “mult”, “power” y “app”
Funciones Recursivas Primitivas Funciones recursivas primitivas: construidas a partir de las funciones iniciales aplicando un número finito de combinaciones, composiciones y recursiones primitivas EJERCICIOS: Realizar ejercicios 1 y 2 del libro
Funciones Recursivas Primitivas Algunas funciones recursivas primitivas: Funciones constantes Correspondencia entre cualquier tupla de 5 elementos y el valor 3 Correspondencia entre cualquier tupla de 3 elementos y el valor 5
Funciones Recursivas Primitivas Algunas funciones recursivas primitivas: Función predecesor Función monus (x-y)
Funciones Recursivas Primitivas Algunas funciones recursivas primitivas: Función equal: Función not: Funciones tabulares:
Funciones Recursivas Primitivas Todas las FRP son totales Existen funciones computables que no son FRP: ¡¡ Div es computable y es parcial !! Los matemáticos pensaron que las FRP abarcaban todas las funciones totales computables.
Funciones Recursivas Primitivas En 1928 Ackermann, presentó una función computable, total y no recursiva primitiva: La función de Ackerman: Las funciones totales computables se conocen como ?-recursivas