Filosofar con estilo

Apuntes para TEORIA DE COMPUTACION Funciones Recursivas.
M. A. Pinninghoff J. Segundo semestre 2006

1. Introducci´n. o El concepto de Funci´n Recursiva fue introducido por Kleene el a˜o o n 1936. Son una clase de funciones num´rico-te´ricas (se llaman as´ las fune o ı ciones f : Nn → N) que pueden ser evaluadas algor´ ıtmicamente. Como Turing, Kleene pretend´ formalizar la noci´n intuitiva deproceıa o dimiento efectivo, aplicada a cantidades num´ricas. e M´s tarde se descubri´ que las funciones de Kleene y las M´quinas de a o a Turing eran formulaciones equivalentes; es decir, que un algoritmo (procedimiento finito) puede ser realizado por una M.T. ssi puede ser expresado como una funci´n recursiva. o Los elementos b´sicos de la definici´n de una funci´n recursiva son: a o o 1) Una base(equivalente a axiomas o condiciones l´ ımite) que establece que ciertos n´meros son, por definici´n, valores de la funci´n para argumenu o o tos dados. 2) Una regla de construcci´n recursiva que nos dice c´mo determinar o o otros valores de la funci´n a partir de valores conocidos. o 3) Una afirmaci´n de que la funci´n s´lo toma aquellos valores que reo o o sultan por aplicaci´n, un n´mero finitode veces, de la regla de construcci´n o u o recursiva sobre los valores de la funci´n b´sica. o a

1

Es decir, una definici´n recursiva especifica un procedimiento efectivo o para evaluar una funci´n siempre que la funci´n est´ definida. o o e Supongamos que consideramos alguna funci´n (n+1)-aria f . El dominio o de f puede ser dividido en pedazos tal que para x1 , . . ., xn tomemos valores fijosy x0 var´ sobre N. Esto es, fijando valores particulares n1 , . . ., nn (para ıe x1 , . . ., xn ) obtenemos una funci´n f (x0 , n1 , . . ., nn ). As´ en vez de trabao ı, jar sobre una funci´n (n+1)-aria f (x0 , x1 , . . ., xn ), podemos trabajar con o muchas funciones unarias f (x0 , n1 , . . ., nn ), una por cada n-tupla (n1 , . . ., nn ). Cuando hacemos esto, estamos tomando a x1 , . . ., xncomo par´metros. a Por ejemplo, supongamos f (x0 , x1 , x2 ) = x0 + (x1 · x2 ), donde x1 y x2 ser´n par´metros. Entonces, a a f (0, x1 , x2 ) = 0 + (x1 · x2 ) f (1, x1 , x2 ) = 1 + (x1 · x2 ) = f (0, x1 , x2 ) + 1 . . . f (n+1, x1 , x2 ) = n+1 + (x1 ·x2 ) = ((x1 ·x2 ) + n) + 1 = f (n, x1 , x2 ) + 1 Recordemos la composici´n de funciones. Si f y g son funciones de una o variable, podemos definir unanueva funci´n h = g ◦ f donde g ◦ f (x) = o g(f (x)). Por ejemplo, si f (x) = x−5 y g(x) = x2 , entonces h(x) = g ◦f (x) = g(f (x)) = g(x − 5) = (x − 5)2 . Podemos extender la idea de composici´n o a varias variables. Supongamos que tenemos f0 , f1 , . . ., fm , las cuales son funciones sobre n+1 variables y g es una funci´n sobre m+1 variables. Eno tonces, podemos definir una nueva funci´n h de n+1variables como: o h(x0 , x1 , . . ., xn ) = g(f0 (x0 , . . ., xn ), f1 (x0 , . . ., xn ), . . ., fm (x0 , . . ., xn )) Si es cierto que f0 , . . ., fm y g son computables, entonces h tambi´n lo es. e 1.1 Definici´n de funciones recursivas primitivas. o Tomaremos como conjunto base, tres funciones que por definici´n decio mos que son recursivas primitivas iniciales:

2

a. Funci´n Nula (ofunci´n cero) o o N (x) = 0, ∀x ∈ N esta funci´n hace corresponder a cualquier n´mero natural el cero. o u b. Funci´n Sucesor o S(x) = x hace corresponder a cualquier n´mero natural x su siguiente, que denou taremos por x . c. Funci´n Proyecci´n (o identidad generalizada) o o Iin (x1 , x2 , . . . , xi , . . . , xn ) = Iin (X) = xi , 1 ≤ i ≤ n hace corresponder a la tupla (x1 , x2 , . . ., xi , . . ., xn) su i-´sima compoe nente. Por ejemplo:
5 I3 (2, 3, 1, 4, 2) = 1 2 I2 (7, 9) = 9 1 I1 (6) = 6

La funci´n I1 es la llamada funci´n identidad. o 1 o Estas tres funciones son totales, puesto que para todo x, N(x), S(x), In (X) est´n perfectamente definidas as´ como su valor asociado. a ı i Adem´s, las tres son computables. a Con estas tres funciones base y las reglas de composici´n y recursi´n...