Función de Ackermann

Función de Ackermann

La función de Ackermann, utilizada en la teoría de la computación, es una función recursiva que toma dos números naturales como argumentos y devuelve un número natural.

Table of contents

1 Definición
2 Recursiva, pero no recursiva primitiva
3 Tabla de Números
4 Descripción explícita

Definición

La función de Ackermann se define por recursividad como sigue:

A(0, n) = n + 1 para n ≥ 0

A(m, 0) = A(m - 1, 1) para m ≥ 1

A(m, n) = A(m - 1, A(m, n - 1)) para m, n ≥ 1

Recursiva, pero no recursiva primitiva

Esta función crece extremadamente rápido. A(4,2) ya tiene 19.729 dígitos. Este crecimiento desmesurado se puede explotar 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.

Tabla de Números

Números de A(m,n)
m\\n 0 1 2 3 4

0 1 2 3 4 5

1 2 3 4 5 6

2 3 5 7 9 11

3 5 13 29 61 125

4 13 65533 2⁶⁵⁵³⁶-3 A(3,2⁶⁵⁵³⁶-3) A(3,A(4,3))

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))

Números de A(m,n)
m\\n	0	1	2	3	4
0	1	2	3	4	5
1	2	3	4	5	6
2	3	5	7	9	11
3	5	13	29	61	125
4	13	65533	2⁶⁵⁵³⁶-3	A(3,2⁶⁵⁵³⁶-3)	A(3,A(4,3))
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))

Descripción explícita

Intuitivamente, la función de Ackermann define la generalización de la multiplicación por dos (sumas iteradas) y la exponenciación con base 2 (productos iterados) hasta la exponenciación iterada, la iteración de la exponenciación iterada, la iteración de la operación anterior, etc. Puede expresarse de forma concisa y no recursiva mediante la notación de flecha de Conway:
A(m,n)=2→(n+3)→(m-2)-3
o los hiper operadoreses:
A(m,n)=hyper(2,m,n+3)-3

Tagoror.com - CineBSO - Radioaficionados.net - Tacoronte Guia - Sector Linux - Deranet

El contenido de Wikipedia se publica bajo la Licencia de Documentación Libre GNU.

Información Legal - Datos de Contacto