Función de Ackermann

Wilhelm Ackermann (29 de marzo 1896 - 24 de diciembre 1962) fue un matemático alemán. Es conocido, sobre todo, por la función de Ackermann nombrada en su honor, un ejemplo importante en la teoría de la computación.

En teoría de la computación, función de Ackermann es una función matemática recursiva encontrada en 1926 por Wilhelm Ackermann, tiene un crecimiento extremadamente rápido, de interés para la ciencia computacional teórica y la teoría de la computabilidad. Hoy en día, hay una serie de funciones que son llamadas funciones Ackermann. Todas ellas tienen una forma similar a la ley original la función de Ackermann y también tienen un comportamiento de crecimiento similar. Esta función toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace Ackerman_IV
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            Application.Exit();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            for (long m = 0; m <= 3; ++m)
            {
                for (long n = 0; n <= 4; ++n)
                {
                    textBox1.AppendText(string.Format("Ackerman({0},{1}) = {2}", m, n, Ackermann(m, n))+"\r\n");            
                }
            }




        }
        public static long Ackermann(long m, long n)
        {
            if (m > 0)
            {
                if (n > 0)
                    return Ackermann(m - 1, Ackermann(m, n - 1));
                else if (n == 0)
                    return Ackermann(m - 1, 1);
            }
            else if (m == 0)
            {
                if (n >= 0)
                    return n + 1;
            }

            throw new System.ArgumentOutOfRangeException();
        }
    }
}

La Función de Ackermann es una función altamente recursiva que no sirve para nada útil, ya que no calcula nada de importancia, la función de Ackermann a menudo se utiliza para probar los niveles de optimización de un compilador. Sin embargo, la manera en la que un compilador genera código para esta función se reduce fácilmente a un par de números que son significativos.

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) es mayor 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 la fila 4, ya no es posible escribir todos los dígitos del resultado de la función.

Una función "A" que recibe dos parámetros m y n, La parte derecha del corchete te indica que vas a hacer con esos dos valores, y bajo que condiciones. Podemos hacer un algoritmo mas o menos así:

// Sintaxis Ackermann(1,1);
funcion Ackermann ( m es entero, n es entero) {

// Evaluamos la primera condicion:

Si m = 0 entonces {
devolver n+1;
}
Si m > 0 y n = 0 entonces {
devolver Ackermann( m-1 , 1)
}

Si m > 0 y n > 0 entonces {
devolver Ackermann( m-1 , Ackermann( m , n - 1));
}
}

https://es.wikipedia.org/wiki/Funci%C3%B3n_de_Ackermann

http://mathworld.wolfram.com/AckermannFunction.html

http://forums.codeguru.com/showthread.php?421680-Ackermann-function-giving-StackOverflowError

https://es.wikipedia.org/wiki/Wilhelm_Ackermann

http://www.programacionfacil.com/estructura_datos_csharp/mecanica_de_recursion.html

https://www.svcommunity.org/forum/cc/funcion-de-ackermann/

http://algoritmobasico.blogspot.com.es/2016/04/algoritmo-de-ackerman-en-java.html

https://rosettacode.org/wiki/Ackermann_function#C.23