La función de Ackermann es el ejemplo más simple de una función total bien definida que es computable pero no recursiva primitiva, proporcionando un contraejemplo a la creencia a principios del siglo XX de que cada función computable también era primitiva recursiva (Dötzel 1991). Crece más rápido que una función exponencial, o incluso una función exponencial múltiple.
La idea básica detrás de la función de Ackermann (que en realidad viene en muchas variantes menores, algunas de las cuales oscurecen esto más que otras) es realmente muy simple, una que incluso ocurre espontáneamente para muchos niños en edad escolar: es solo la idea de extrapolar la secuencia , donde cada operación equivale a la aplicación repetida de la operación anterior.
Es decir, recuerde que, para enteros positivos x e y, tenemos que x * y = el resultado de + ing y muchas xs, y x ^ y = el resultado de * ing y muchas xs.
Extendiendo esto, podríamos definir una nueva operación x # y = el resultado de ^ y y muchas xs. [Sin embargo, como ^ no es asociativo, necesitamos hacer una convención aquí en cuanto a si eso significa “asociativo a la izquierda” … ((((x ^ x) ^ x) ^ x) … ^ x con y muchas xs, o ” asociativo a la derecha “x ^ (x ^ (x ^… x)) con y muchas xs. Pero tenga en cuenta que la versión asociativa izquierda es igual a x ^ (x ^ (y-1)), lo que no es terriblemente interesante además del operador ^ que ya tenemos. Entonces, la convención que elegiremos es definir x # y como el resultado de ^ y muchas xs asociativas a la derecha]. Entonces 2 # 4 = 2 ^ (2 ^ (2 ^ 2)) = 65536, por ejemplo.
- ¿Por qué cualquier gráfico conectado con exactamente dos vértices impares es transitable o euleriano?
- Cómo crear un algoritmo que pueda determinar si un punto está contenido en un polígono irregular definido por los puntos de sus esquinas
- ¿Cómo resolverías 1,3,6 y 10 usando las fórmulas recursivas y explícitas?
- Si [matemáticas] | A \ copa B | = K [/ math], entonces, ¿cuál es el número de elementos en [math] A \ cap B [/ math] + el número de elementos en [math] B \ cap A [/ math]?
- ¿Cuál es el número más alto en matemáticas?
Y luego podemos definir x $ y como el resultado de #ing y muchos xs (asociativo a la derecha nuevamente, como siempre), y luego definir x% y como el resultado de $ ing y muchos xs, y así hasta el infinito.
Por supuesto, no es necesario seguir creando nuevos símbolos; en su lugar, podemos describir cuántos niveles de iteración de este proceso hemos pasado: x [1] y significará x + y, x [2] y significará x * y, x [3] y significará x ^ y, x [4] y significará x # y, etc.
Entonces ahora tenemos una función de tres argumentos, x [N] y. Esta es esencialmente la función de Ackermann (aunque, como dije, hay muchas variantes menores en esto que también se llaman funciones de Ackermann; los detalles específicos que cambian de autor a autor en realidad no importan demasiado para nada (particularmente populares son dos versiones de argumento que esencialmente arreglan la x aquí para que siempre sea 2)). Como sucede, crece súper rápido; 4 [5] 3, por ejemplo, es 4 # (4 # 4) = 4 # (4 ^ 4 ^ 4 ^ 4) = 4 ^ 4 ^ 4 ^ 4 ^ 4 ^… ^ 4, con 4 ^ 4 ^ 4 ^ 4 muchos 4s = manera súper jodidamente enorme.
La relación con las funciones recursivas primitivas es que es bastante fácil mostrar inductivamente que la función f (x, y) = x [N] y “crece más rápido” que cualquier función definida por menos de N niveles de recursividad primitiva anidada. Pero, por supuesto, la función de Ackermann en sí misma, con la elección apropiada del argumento del medio, crece tan rápido como x [N] y para valores arbitrariamente grandes de N; en consecuencia, la función de Ackermann no puede definirse por ningún número finito de recursiones primitivas, y por lo tanto no es primitiva recursiva.
Dicho esto, si el objetivo de uno es solo mostrar la existencia de funciones computables totales que no son primitivas recursivas, esto también es mucho más fácil de hacer sin molestarse con la función de Ackermann en primer lugar: uno puede enumerar computacionalmente la recursiva primitiva funciones y luego diagonalizarlas para obtener una función computable total que no está entre ellas.
(Esta es esencialmente la observación de que el Problema de detención es trivial para las funciones recursivas primitivas (cada función recursiva primitiva se detiene en cada entrada) y, por lo tanto, por la indisputabilidad del Problema de detención para las funciones computables generales, se encuentra una función computable que no es primitivo recursivo).