No tengo

Solo disponible en BuenasTareas
  • Páginas : 4 (992 palabras )
  • Descarga(s) : 0
  • Publicado : 17 de octubre de 2010
Leer documento completo
Vista previa del texto
En teoría de la computación, la función de Ackermann es una función recursiva que toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define comosigue:

Ahora bien, a efectos pedagógicos se puede utilizar una versión alternativa:

Donde s(x) es la función sucesor y fn(x) es la función potencia (aquella que aplica f n veces).
* |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 lleva a cabo por reducciónal absurdo y utilizando el lema de que toda función recursiva primitiva está mayorada por una función Ackermann.

Comenzamos suponiendo que , por tanto
Usando el lema de la mayoración, debeexistir un k tal que

Pero entonces, como esto vale para todo x, también valdrá para x=k
, usando la definición, llegamos a que:

Lo cual es absurdo.
Esta función crece extremadamente rápido: elvalor 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, ypor ello no es recursiva primitiva.
Tabla de valores
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 |   | A(3,265536-3) | A(3,A(4,3)) | (n + 3 términos) |
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)) | |
Para darse una idea de la magnitud de los valores que aparecen de la fila 4 en adelante, se puede destacar que por ejemplo, A(4, 2) esmayor que el número de partículas que forman el universo elevado a la potencia 200 y el resultado de A(5, 2) no se puede escribir dado que no cabría en el Universo físico. En general, por debajo de...
tracking img