Informe Recursividad Funcion Ackerman 4l1f63

RECURSIVIDAD DE LA FUNCIÓN ACKERMANN

WILIAN FERNANDO PANTOJA CARVAJAL CÓDIGO: 46091097

Presentado a: Ingeniero RICARDO ANTONIO ZAMBRANO SEGURA En la materia Laboratorio Estructuras de Datos II.

UNIVERSIDAD DEL CAUCA FACULTAD DE INGENIERÍA ELECTRÓNICA Y TELECOMUNICACIONES PROGRAMA INGENERÍA DE SISTEMAS Popayán, Marzo de 2011

INFORME DE LABORATORIO No. 1: RECURSIVIDAD DE LA FUNCIÓN ACKERMANN

La recursividad consiste en el cuerpo de sentencias del sub algoritmo que se invoca al propio sub algoritmo para resolver “una versión más pequeña” del problema original. Habrá un caso (o varios) tan simple que pueda resolverse directamente. Es una alternativa diferente para implementar estructuras de repetición. FUNCION ACKERMANN: Función recursiva que toma dos números naturales como argumentos y devuelve un número natural. Se define así:

PROPIEDADES:



Sea



Sea



Sea



Sea



Además la función de Ackerman (ACK(x) = fx(x)) no es FRP (función recursiva primitiva). La demostración de este teorema se

, (FRP = Función recursiva primitiva). . . .

lleva a cabo por reducción al absurdo y utilizando el lema de que toda función recursiva primitiva está mayorada por una función Ackermann.



Comenzamos suponiendo que



Usando el lema de la mayoración, debe existir un k tal que



Pero entonces, como esto vale para todo x, también valdrá para x=k



, por tanto

, usando la definición, llegamos a que:

 

Lo cual es absurdo.



Esta función crece extremadamente rápido: el valor A(4,2) ya tiene 19.729 dígitos. Este crecimiento desmesurado se puede utilizar para demostrar que la función computable f(n) = A(n,n) crece más rápido que cualquier función recursiva primitiva, y por ello no es recursiva primitiva.

EJEMPLOS DE LA FUNCION ACKERMANN:

Números de A(m,n)

m\n

0

1

2

3

4

n

0

1

2

3

4

5

n+1

1

2

3

4

5

6

n+2

2

3

5

7

9

11

2n + 3

3

5

13

29

61

125

4

13

65533

5

65533 A(4,65533) A(4,A(5,1))

A(4,A(5,2)) A(4,A(5,3))

6

A(5,1) A(5,A(5,1)) A(5,A(6,1))

A(5,A(6,2)) A(5,A(6,3))

A(3,265536-3) A(3,A(4,3))

(n + 3 términos)

BIBLIOGRAFÍA 

Función de Ackermann. Wikipedia, http://es.wikipedia.org/wiki/Funci%C3%B3n_de_Ackermann.

en

línea:

URL: