ingenieria

Lógica Superior:

Computabilidad e Incompletitud
Profesor: Eduardo Barrio
UBA - Filosofía
2do cuatrimestre de 2012

Funciones y computabilidad
¿Qué funciones son computables?
Tesis de Church:
Cualquier función efectivamente computable es una función
recursiva.

Funciones Recursivas
Funciones Computables:
- Funciones computables por M Turing
- Funciones recursivas

¿Qué es unafunción?
Relación entre dos conjuntos
Para todo valor en un dominio se asigna un (y sólo un) elemento en
codominio.
f(x):

0 si x es 0
1 si x es mayor que 0

Hay dos condiciones que se deben cumplir para calcular la función

Funciones Recursivas

Funciones Efectivamente Computables:
- funciones para las cuales hay reglas explícitas bien definidas que al
ser seguidas permitirían (enprincipio) calcular el valor de una función

Funciones Recursivas
¿Qué funciones son computables?
Recursividad: descomponer un problema
para encontrar una solución en los
componentes simples.
Descomposición que permite encontrar
mecánicamente el valor de la función.

Funciones Recursivas
f(x) =

si x=0, entonces f(x):1
si x mayor a 0, entonces f(x) = x . f(x-1)

f(1) =

six=1, entonces f(x):1

f(3) =

si x=3, entonces f(3) = 3 . f(3-1)

f(3) = 3 . f(2)
3 . f(2) = x . f(x-1) = 2 . f(2-1) = 2 . f(1) = 2 . 1 = 2
3.2 = 6

Funciones Recursivas
f(x) =

si x=0, entonces f(x):1
si x mayor a 0, entonces f(x) = x . f(x-1)

Hay un algoritmo tal que para cualquier valor que tome f(x),
en un número finito de pasos, nos permite calcular su valor.

FuncionesRecursivas
Las funciones recursivas coinciden con las funciones Turing-computables.
Un subconjunto importante de las funciones recursivas es el de las funciones recursivas primitivas (PR)
1

- Las Funciones PR son un subconjunto de las Funciones recursivas.

2

- Las Funciones PR son siempre funciones totales:

3

- Incluyen a las funciones aritméticas más comunes
1

- Sucesor

2- Suma

3

- Multiplicación

4

- División

5

- Potencia

6

- Factorial

Recursividad
¿Qué es una función recursiva?

Simplemente se identifica un conjunto (obviamente) computable de funciones básicas que
junto con algunas operaciones mecánicas (composición, recursión primitiva y minimización)
generan nuevas funciones (que son recursivas).

Recursión
- Descomponer unafunción en sus componentes básicos.
- Reducir una función a sus funciones constitutivas.
- Eliminar una función a favor de sus funciones constitutivas.

Recursividad
Función Recursiva: exponenciación

53 :

5x5x5x1

:

(1 + 1 + 1+ 1+ 1 , ..., + 1)
125 (el sucesor de x, 125 veces)

Exp.

Recusión
- Escribir una función en sus componentes más básicos

CLASE DE FUNCIONESRECURSIVAS PRIMITIVAS

1) Funciones Básicas (Unidades Atómicas)
z(0) = 0 , z(0’’’’’’’) = 0
s(0) = 0‘
id11 (x) = x

s(0’) = 0’’
id21 (x,y) = x

id22 (x,y) = y

2) Operaciones de Construcción:
• Composición :

componer dos funciones recursivas da otra función que es recursiva

• Recursión Primitiva: componer recursivamente una nueva función desde una función recursiva da otra
funciónrecursiva.
- caso base
- cláusula de recursión.
• Minimización: para computar Mn[f](x), se computa f(x, 0), f(x, 1), ... hasta que se encuentra un y tal que f(x, y) = 0.
Si hay tal y, entonces Mn[f](x) = el menor y;
Si no hay tal y, entonces Mn[f](x) es indefinido.
3) Nada pertenece a la clase si no es una función primitiva o construída por medio de composición o recursión.

CLASE DEFUNCIONES RECURSIVAS PRIMITIVAS

1) Funciones Básicas (Unidades Atómicas)
Funciones recursivas Básicas: z(x), s(x) and idk
Composición
Supongamos que f es una función de m argumentos PR y cada g1,..., gm es una función de n argumentos.
Entonces obtenemos la función compuesta:
h(x1,..., xn ) = f(g1(x1,..., xn ), ..., gm(x1,..., xn))
Recursión primitiva
h se define por recursión primitiva desde...