No tengo

Páginas: 4 (992 palabras) Publicado: 17 de octubre de 2010
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...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • No tengo
  • No tengo
  • No Tengo
  • yo te tengo
  • no tengo
  • NO TENGO
  • No Tengo
  • No Tengo

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS