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