Funciones recursivas. Se dice que una función está definida recursivamente o es una función recursiva si su regla de definición se refiere a sí mis...

Funciones recursivas. Se dice que una función está definida recursivamente o es una función recursiva si su regla de definición se refiere a sí misma. Debido a esta autoreferencia, a veces es difícil saber si una función recursiva dada está bien definida. Las funciones recursivas son de gran importancia en la teoría de la computación en la ciencia computacional. Ejemplo 5.9.6 Función 91 de McCarthy. La siguiente función M : Z Z fue definida por John McCarthy, un pionero en la teoría de la computación y en el estudio de la inteligencia artificial: M n n ฀ 10 si n 100 M M n 11 si n 100 para todos los enteros positivos n. Encuentre M(99). Solución Por el uso repetido de la definición de M, M(99)= M(M(110))= M(100)= M(M(111))= M(101)= 91 ya que 99 100 ya que 110 100 ya que 100 100 ya que 111 100 ya que 101 100 Lo notable de esta función es que se toma el valor 91 para todos los enteros positivos menores o iguales a 101. (Se le pedirá demostrar esto en el ejercicio 20 al final de esta sección.) Por supuesto, para n 101, M(n) está bien definido ya que es igual a n ฀ 10. Ejemplo 5.9.7 La función de Ackermann. En la década de 1920 el lógico y matemático alemán Wilhelm Ackermann definió por primera vez una versión de la función que ahora lleva su nombre. Esta función es importante en la ciencia computacional porque ayuda a responder a la pregunta de qué se puede y qué no se puede calcular con una computadora. Se define en el conjunto de todos los pares de números enteros no negativos de la siguiente manera: A(0, n) = n + 1 A(m, 0) = A(m − 1, 1) A(m, n) = A(m − 1, A(m, n − 1)) para todo entero no negativo n 5.9.1 para todo entero positivo m 5.9.2 para todo entero positivo m y n 5.9.3 Determine A(1, 2). Solución A(1, 2)= A(0, A(1, 1))= A(0, A(0, A(1, 0)))= A(0, A(0, A(0, 1)))= A(0, A(0, 2))= A(0, 3)= 4 por (5.9.3) con m 1 y n 2 por (5.9.3) con m 1 y n 1 por (5.9.2) con m 1 por (5.9.1) con n 1 por (5.9.1) con n 2 por (5.9.1) con n 3. Las propiedades especiales de la función de Ackermann son una consecuencia de su tasa de crecimiento fenomenal. Mientras que los valores de A(0, 0) 1, A(l, 1) 3, A(2, 2) 7 y A(3, 3) 61 no son especialmente impresionantes, A(4, 4) ∼= 22265536 y los valores de A(n, n) continúan aumentando con una rapidez extraordinaria. El argumento es un poco técnico, pero no es difícil demostrar que la función de Ackermann está bien definida. El siguiente es un ejemplo de una “definición” recursiva que no define una función. Ejemplo 5.9.8 Una “función” recursiva no está bien definida. Considere el siguiente intento de definir una función recursiva G de Z a Z. Para todo entero n 1, G(n) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 1 + G (n 2) G(3n − 1) si n es 1 si n es par si n es impar y n 1. ¿G está bien definida? ¿Por qué? Solución Supongamos que G es una función. Entonces, por definición de G, G(1) = 1, G(2) = 1 + G(1) = 1 + 1 = 2, G(3) = G(8) = 1 + G(4) = 1 + (1 + G(2)) = 1 + (1 + 2) = 4, G(4) = 1 + G(2) = 1 + 2 = 3. Sin embargo, G(5) = G(14) = 1 + G(7) = 1 + G(20) = 1 + (1 + G(10)) = 1 + (1 + (1 + G(5))) = 3 + G(5). Restando G(5) de ambos lados se obtiene 0 3, que es falso. Dado que la suposición de que G es una función conduce lógicamente a un enunciado falso, se deduce que G no es una función. Una ligera modificación de la fórmula del ejemplo 5.9.8 produce una “función”, cuyo estado de definición es desconocido. Considere la siguiente fórmula: Para todo entero n 1, T (n) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 T (n 2) T (3n + 1) si n es 1 si n es par si n es impar. En la década de 1930, un estudiante, Luther Collatz, se interesó en el comportamiento de una función relacionada g, que se define de la siguiente manera: g(n) n 2 si n es par y g(n) 3n 1 si n es impar. Collatz supone que para cualquier número positivo inicial n, el cálculo de los valores sucesivos de g(n), g2(n), g3(n), . . . finalmente produce el número 1. Determine si esta suposición es verdadera o falsa que se llama problema 3n 1 (o el problema 3x 1). Si la suposición de Collatz es verdadera, la fórmula para T define una función, si la suposición es falsa, T no está bien definida. Desde la publicación de este libro, la respuesta no es conocida, a pesar de que el cálculo por computadora ha establecido que es válido para valores muy grandes de n.