função de Ackermann

Na teoria da computabilidade, a Função de Ackermann, nomeada por Wilhelm Ackermann, é um dos mais simples e recém-descobertos exemplos de uma função computável que não são funções recursivas primitivas. Todas as funções recursivas primitivas são totais e computáveis, mas a Função de Ackermann mostra que nem toda função total-computável é recursiva primitiva. Depois que Ackermann publicou sua função (que continha três inteiros positivos como argumentos), vários autores a modificaram para atender a várias finalidades. Então, a função de Ackermann atual pode ser referenciada a uma de suas várias formas da função original. Uma das versões mais comuns, a função de Ackermann-Péter (com dois argumentos), é definida a seguir para os inteiros não negativos m e n: Como se pode ver, seu valor cresce rapidamente, até mesmo para pequenas entradas. Por exemplo, A(4,2) resulta em um inteiro com 19.729 dígitos.