Função de Ackermann

Question book.svg
Este artigo ou secção não cita fontes confiáveis e independentes (desde Dezembro de 2012). Ajude a inserir referências.
O conteúdo não acadêmico)

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.

História

No final dos anos 20, os matemáticos Gabriel Sudan e Wilhelm Ackermann, alunos de David Hilbert, estavam estudando os fundamentos da computação. Os dois levaram os créditos por terem descoberto as funções computáveis totais que não são recursivas primitivas. Sudan publicou sua própria função, menos conhecida. Logo depois, em 1928, Ackermann publicou sua função . A função de Ackermann de três argumentos, , é definida de tal forma que, para p = 0, 1 ou 2, ela reproduz as funções básicas de adição, multiplicação e exponenciação, como:

e para p > 2, ela estende essas três operações básicas de modo que possa ser expresso pela Notação de Knuth como:

(Além de seu papel histórico como uma função computável não recursiva primitiva, a função original de Ackermann é vista como uma extensão das funções aritméticas básicas além da exponenciação, embora não como suas variantes, que são projetadas especificamente para esse fim, como a sequência de hiperoperação de Goodstein.

Rózsa Péter e Raphael Robinson desenvolveram, mais tarde, a versão com apenas duas variáveis da função de Ackermann, que se tornou a preferida de vários autores.