En la teoría de la computabilidad , una función recursiva primitiva es, en términos generales, una función que puede ser calculada por un programa de computadora cuyos bucles son todos bucles "for" (es decir, se puede determinar un límite superior del número de iteraciones de cada bucle antes de ingresar a la círculo). Las funciones recursivas primitivas forman un subconjunto estricto de aquellas funciones recursivas generales que también son funciones totales .
La importancia de las funciones recursivas primitivas radica en el hecho de que la mayoría de las funciones computables que se estudian en teoría de números (y más generalmente en matemáticas) son recursivas primitivas. Por ejemplo, la suma y la división , la función factorial y exponencial y la función que devuelve el n- ésimo primo son todas primitivas recursivas. [1] De hecho, para mostrar que una función computable es recursiva primitiva, basta con mostrar que su complejidad temporal está limitada por una función recursiva primitiva del tamaño de entrada. De ello se deduce que es difícil idear una función computable que seano primitivo recursivo, aunque se conocen algunos (ver § Limitaciones más adelante).
El conjunto de funciones recursivas primitivas se conoce como PR en la teoría de la complejidad computacional .
Definición
Las funciones recursivas primitivas se encuentran entre las funciones teóricas de números, que son funciones de los números naturales (enteros no negativos) {0, 1, 2, ...} a los números naturales. Estas funciones toman n argumentos para algún número natural n y se denominan n - ario .
Las funciones recursivas primitivas básicas vienen dadas por estos axiomas :
- Función constante : La función 0-aria constante 0 es primitiva recursiva.
- Función sucesora : La función sucesora 1-aria S , que devuelve el sucesor de su argumento (ver postulados de Peano ), es primitiva recursiva. Es decir, S ( k ) = k + 1.
- Función de proyección : Un par i ≥1 yn ≥ i , define una función n -aria: P i n ( x 1 , ..., x n ) = x i , tal función es primitiva recursiva.
Se pueden obtener funciones recursivas primitivas más complejas aplicando las operaciones dadas por estos axiomas:
- Composición : Dada una función recursiva primitiva k -ary f , y un número k de funciones recursivas primitivas m -ary g 1 , ..., g k , la composición de f con g 1 , ..., g k , es decir, la m -función es primitivo recursivo.
Ejemplo. Tomamos f ( x ) como el S ( x ) definido anteriormente. Esta f es una función recursiva primitiva 1-aria. Y también lo es g ( x ) = S ( x ). Entonces, h ( x ) definida como f ( g ( x )) = S ( S ( x )) también es una función primitiva recursiva 1-aria. Hablando informalmente, h ( x ) es la función que convierte x en x +2.
- Recursión Primitive : Dada f , un k función recursiva primitiva ary, y g , a ( k 2) ary función recursiva primitiva, el ( k 1) ary función h se define como la recursión primitiva de f y g , es decir, la función h es recursiva primitiva cuando
- y
Ejemplo. Suponga que f ( x ) = P 1 1 ( x ) = x y g ( x , y , z ) = S ( P 2 3 ( x , y , z )) = S ( y ). Entonces h (0, x ) = x y h ( S ( y ), x ) = g ( y , h ( y , x ), x ) = S ( h ( y , x )). Ahora h (0,1) = 1, h (1,1) = S ( h (0,1)) = 2, h (2,1) = S ( h (1,1)) = 3. Esta h es una función recursiva primitiva de 2 arias. Podemos llamarlo 'adición'.
Interpretación. La función h actúa como un bucle for desde 0 hasta el valor de su primer argumento. El resto de los argumentos para h , denotados aquí con x i 's ( i = 1, ..., k ), son un conjunto de condiciones iniciales para el bucle For que puede utilizar durante los cálculos pero que son inmutables por eso. Las funciones f y g en el lado derecho de las ecuaciones que definen h representan el cuerpo del ciclo, que realiza cálculos. La función f solo se usa una vez para realizar los cálculos iniciales. Los cálculos para los pasos subsiguientes del bucle son realizados por g . El primer parámetro de g se alimenta con el valor "actual" del índice del bucle For. El segundo parámetro de g se alimenta con el resultado de los cálculos previos del bucle For, de los pasos anteriores. El resto de los parámetros para g son las condiciones iniciales inmutables para el bucle For mencionado anteriormente. Pueden ser usados por g para realizar cálculos pero ellos mismos no serán alterados por g .
Las funciones recursivas primitivas son las funciones básicas y las que se obtienen de las funciones básicas aplicando estas operaciones un número finito de veces.
Papel de las funciones de proyección
Las funciones de proyección se pueden utilizar para evitar la aparente rigidez en cuanto a la aridad de las funciones anteriores; Al usar composiciones con varias funciones de proyección, es posible pasar un subconjunto de los argumentos de una función a otra función. Por ejemplo, si g y h son funciones recursivas primitivas de 2 arias, entonces
también es primitivo recursivo. Una definición formal que utiliza funciones de proyección es
Conversión de predicados en funciones numéricas
En algunos entornos, es natural considerar funciones recursivas primitivas que toman como entradas tuplas que mezclan números con valores de verdad (es decir, t para verdadero yf para falso), o que producen valores de verdad como salidas. [2] Esto se puede lograr identificando los valores de verdad con números de cualquier manera fija. Por ejemplo, es común identificar el valor de verdad t con el número 1 y el valor de verdad f con el número 0. Una vez realizada esta identificación, la función característica de un conjunto A , que siempre devuelve 1 o 0, puede ser visto como un predicado que indica si un número está en el conjunto a . Esta identificación de predicados con funciones numéricas se asumirá en el resto de este artículo.
Definición de lenguaje informático
Un ejemplo de un lenguaje de programación recursivo primitivo es uno que contiene operadores aritméticos básicos (por ejemplo, + y -, o AGREGAR y RESTA), condicionales y comparación (SI-ENTONCES, IGUALES, MENOS-QUE) y bucles acotados, como el básico bucle for , donde hay un límite superior conocido o calculable para todos los bucles (FOR i FROM 1 TO n, sin i ni n modificables por el cuerpo del bucle). No se admiten estructuras de control de mayor generalidad, como los bucles while o IF-THEN más GOTO , en un lenguaje recursivo primitivo. Douglas Hofstadter 's BLOOP en Gödel, Escher, Bach es un lenguaje de este tipo. Agregar bucles ilimitados (WHILE, GOTO) hace que el lenguaje sea recursivo general y Turing-completo , al igual que todos los lenguajes de programación de computadoras del mundo real.
La definición de funciones recursivas primitivas implica que su cálculo se detiene en cada entrada (después de un número finito de pasos). Por otro lado, el problema de la detención es indecidible para funciones recursivas generales, incluso si son totales . Es decir, hay programas que se detienen en cada entrada, pero para los que esto no puede ser verificado por un algoritmo.
Ejemplos de
La mayoría de las funciones de teoría numérica definibles mediante la recursividad en una sola variable son recursivas primitivas. Los ejemplos básicos incluyen las funciones de suma y resta truncada .
Adición
Intuitivamente, la suma se puede definir de forma recursiva con las reglas:
- ,
Para encajar esto en una definición recursiva primitiva estricta, defina:
Aquí S ( n ) es "el sucesor de n " (es decir, n +1), P 1 1 es la función de identidad y P 2 3 es la función de proyección que toma 3 argumentos y devuelve el segundo. Funciones f y g requeridas por la definición anterior de la operación de recursión primitiva se reproducen respectivamente por P 1 1 y la composición de S y P 2 3 .
Sustracción
Debido a que las funciones recursivas primitivas usan números naturales en lugar de enteros, y los números naturales no se cierran con la resta, se estudia una función de resta truncada (también llamada "resta propia") en este contexto. Esta función de resta limitada sub ( a , b ) [o b ∸ a ] devuelve b - a si no es negativo y devuelve 0 en caso contrario.
La función predecesora actúa como lo opuesto a la función sucesora y se define de forma recursiva por las reglas:
- pred (0) = 0,
- pred ( n + 1) = n .
Estas reglas se pueden convertir en una definición más formal mediante recursividad primitiva:
- pred (0) = 0,
- pred (S ( n )) = P 1 2 ( n , pred ( n )).
La función de resta limitada se puede definir a partir de la función predecesora de una manera análoga a la forma en que se define la suma a partir del sucesor:
- sub (0, x ) = P 1 1 ( x ),
- sub (S ( n ), x ) = pred ( P 2 3 ( n , sub ( n , x ), x )).
Aquí sub ( a , b ) corresponde a b ∸ a ; En aras de la simplicidad, el orden de los argumentos se ha cambiado de la definición "estándar" para ajustarse a los requisitos de la recursividad primitiva. Esto podría rectificarse fácilmente utilizando una composición con proyecciones adecuadas.
Otras operaciones sobre números naturales
Las pruebas de exponenciación y primalidad son primitivas recursivas. Dada primitiva funciones recursivas e , f , g , y h , una función que devuelve el valor de g cuando e ≤ f y el valor de h de otro modo es recursiva primitiva.
Operaciones con enteros y números racionales
Mediante el uso de numeraciones de Gödel , las funciones recursivas primitivas pueden extenderse para operar en otros objetos como enteros y números racionales . Si los números enteros están codificados por números de Gödel de forma estándar, las operaciones aritméticas, incluidas la suma, la resta y la multiplicación, son todas recursivas primitivas. De manera similar, si los racionales están representados por números de Gödel, entonces las operaciones de campo son todas recursivas primitivas.
Uso en aritmética de Peano de primer orden
En la aritmética de Peano de primer orden , hay infinitas variables (símbolos arios-0) pero no símbolos no lógicos k-arios con k> 0 distintos de S, +, * y ≤. Por lo tanto, para definir funciones recursivas primitivas, uno tiene que usar el siguiente truco de Gödel.
Al usar una numeración de Gödel para secuencias , por ejemplo, la función β de Gödel , cualquier secuencia finita de números puede codificarse con un solo número. Por lo tanto, tal número puede representar la función recursiva primitiva hasta un n dado.
Sea h una función de recursión primitiva aria definida por:
donde C es una constante yg es una función ya definida.
Usando la función β de Gödel, para cualquier secuencia de números naturales (k 0 , k 1 ,…, k n ), existen números naturales byc tales que, para todo i ≤ n, β (b, c, i) = k yo . Por tanto, podemos utilizar la siguiente fórmula para definir h ; más precisamente, m = h ( n ) es una abreviatura de lo siguiente:
y la igualación ag , ya definida, es de hecho una abreviatura de alguna otra fórmula ya definida (como es β, cuya fórmula se da aquí ).
La generalización a cualquier función de recursión primitiva k-ary es trivial.
Relación con funciones recursivas
La clase más amplia de funciones recursivas parciales se define mediante la introducción de un operador de búsqueda ilimitado . El uso de este operador puede resultar en una función parcial , es decir, una relación con como máximo un valor para cada argumento, pero no necesariamente tiene ningún valor para ningún argumento (ver dominio ). Una definición equivalente establece que una función recursiva parcial es aquella que puede ser calculada por una máquina de Turing . Una función recursiva total es una función recursiva parcial que se define para cada entrada.
Toda función recursiva primitiva es recursiva total, pero no todas las funciones recursivas totales son recursivas primitivas. La función de Ackermann A ( m , n ) es un ejemplo bien conocido de una función recursiva total (de hecho, total demostrable), que no es recursiva primitiva. Hay una caracterización de las funciones recursivas primitivas como un subconjunto de las funciones recursivas totales usando la función de Ackermann. Esta caracterización establece que una función es recursiva primitiva si y solo si hay un número natural m tal que la función pueda ser calculada por una máquina de Turing que siempre se detiene dentro de A ( m , n ) o menos pasos, donde n es la suma de los argumentos de la función recursiva primitiva. [3]
Una propiedad importante de las funciones recursivas primitivas es que son un subconjunto recursivamente enumerable del conjunto de todas las funciones recursivas totales (que en sí mismo no es recursivamente enumerable). Esto significa que hay una única función computable f ( m , n ) que enumera las funciones recursivas primitivas, a saber:
- Para cada función recursiva primitiva g , hay un m tal que g ( n ) = f ( m , n ) para todo n , y
- Para cada m , la función h ( n ) = f ( m , n ) es primitiva recursiva.
f se puede construir explícitamente repitiendo iterativamente todas las formas posibles de crear funciones recursivas primitivas. Por lo tanto, es demostrablemente total. Se puede usar un argumento de diagonalización para mostrar que f no es una primitiva recursiva en sí misma: si lo hubiera sido, también lo sería h ( n ) = f ( n , n ) +1. Pero si esto es igual a alguna función recursiva primitiva, hay una m tal que h ( n ) = f ( m , n ) para todo n , y luego h ( m ) = f ( m , m ), lo que lleva a la contradicción.
Sin embargo, el conjunto de funciones recursivas primitivas no es el subconjunto enumerable recursivamente más grande del conjunto de todas las funciones recursivas totales. Por ejemplo, el conjunto de funciones demostrablemente totales (en la aritmética de Peano) también es recursivamente enumerable, ya que se pueden enumerar todas las pruebas de la teoría. Si bien todas las funciones recursivas primitivas son probablemente totales, lo contrario no es cierto.
Limitaciones
Las funciones recursivas primitivas tienden a corresponder muy de cerca con nuestra intuición de lo que debe ser una función computable. Ciertamente, las funciones iniciales son intuitivamente computables (en su misma simplicidad), y las dos operaciones mediante las cuales se pueden crear nuevas funciones recursivas primitivas también son muy sencillas. Sin embargo, el conjunto de funciones recursivas primitivas no incluye todas las funciones computables totales posibles; esto se puede ver con una variante del argumento diagonal de Cantor . Este argumento proporciona una función computable total que no es recursiva primitiva. Un bosquejo de la prueba es el siguiente:
Ahora defina la "función evaluadora" ev con dos argumentos, por ev ( i , j ) = f i ( j ) . Claramente, ev es total y computable, ya que uno puede determinar efectivamente la definición de f i , y siendo una función recursiva primitiva f i es en sí misma total y computable, por lo que f i ( j ) siempre está definida y efectivamente computable. Sin embargo, un argumento diagonal mostrará que la función ev de dos argumentos no es recursiva primitiva.
Supongamos que ev fuera recursiva primitiva, entonces la función unaria g definida por g ( i ) = S ( ev ( i , i )) también sería recursiva primitiva, como se define por composición de la función sucesora y ev . Pero entonces g aparece en la enumeración, por lo que hay un número n tal que g = f n . Pero ahora g ( n ) = S ( ev ( n , n )) = S ( f n ( n )) = S ( g ( n )) da una contradicción.Este argumento se puede aplicar a cualquier clase de funciones computables (totales) que se puedan enumerar de esta manera, como se explica en el artículo Máquina que siempre se detiene . Sin embargo, tenga en cuenta que las funciones computables parciales (aquellas que no necesitan definirse para todos los argumentos) se pueden enumerar explícitamente, por ejemplo, enumerando las codificaciones de la máquina de Turing.
Se conocen otros ejemplos de funciones recursivas totales pero no recursivas primitivas:
- La función que lleva m a Ackermann ( m , m ) es una función recursiva total unaria que no es recursiva primitiva.
- El teorema de Paris-Harrington implica una función recursiva total que no es recursiva primitiva. Debido a que esta función está motivada por la teoría de Ramsey , a veces se considera más "natural" que la función de Ackermann.
- La función de Sudán
- La función de Goodstein
Algunas funciones recursivas primitivas comunes
- Los siguientes ejemplos y definiciones son de Kleene (1952) págs. 223-231; muchos aparecen con pruebas. La mayoría también aparecen con nombres similares, ya sea como pruebas o como ejemplos, en Boolos-Burgess-Jeffrey 2002 pp. 63–70; agregan el logaritmo lo (x, y) o lg (x, y) dependiendo de la derivación exacta.
A continuación observamos que las funciones recursivas primitivas pueden ser de cuatro tipos:
- funciones para abreviar: "funciones teóricas de números" de {0, 1, 2, ...} a {0, 1, 2, ...},
- predicados : de {0, 1, 2, ...} a valores de verdad {t = verdadero, f = falso},
- conectivos proposicionales : desde los valores de verdad {t, f} hasta los valores de verdad {t, f},
- representar funciones : desde valores de verdad {t, f} hasta {0, 1, 2, ...}. Muchas veces un predicado requiere una función de representación para convertir la salida del predicado {t, f} a {0, 1} (observe que el orden "t" a "0" y "f" a "1" coincide con ~ sg () definido debajo). Por definición, una función φ ( x ) es una "función de representación" del predicado P ( x ) si φ toma solo los valores 0 y 1 y produce 0 cuando P es verdadero ".
A continuación, la marca "'", por ejemplo, a', es la marca primitiva que significa "el sucesor de", generalmente considerada como "+1", por ejemplo, a +1 = def a '. Las funciones 16-20 y #G son de particular interés con respecto a convertir predicados recursivos primitivos y extraerlos de su forma "aritmética" expresada como números de Gödel .
- Suma: a + b
- Multiplicación: a × b
- Exponenciación: a b
- Factorial a! : 0! = 1, a '! = a! × a '
- pred (a): (Predecesor o decremento): Si a> 0 entonces a-1 else 0
- Resta adecuada a ∸ b: Si a ≥ b entonces ab else 0
- Mínimo (a 1 , ... a n )
- Máximo (a 1 , ... a n )
- Diferencia absoluta: | ab | = def (a ∸ b) + (b ∸ a)
- ~ sg (a): NOT [signum (a)]: Si a = 0 entonces 1 else 0
- sg (a): signum (a): Si a = 0 entonces 0 else 1
- a | b: (a divide b): Si b = k × a para algún k entonces 0 else 1
- Resto (a, b): el sobrante si b no divide a "uniformemente". También llamado MOD (a, b)
- a = b: sg | a - b | (La convención de Kleene era representar verdadero por 0 y falso por 1; actualmente, especialmente en computadoras, la convención más común es la inversa, es decir, representar verdadero por 1 y falso por 0, lo que equivale a cambiar sg en ~ sg aquí y en el siguiente elemento)
- a
- Pr (a): a es un número primo Pr (a) = def a> 1 & NOT (existe c) 1
[c | a] - p i : el i + 1-st número primo
- (a) i : exponente de p i en a: la única x tal que p i x | a & NOT (p i x ' | a)
- lh (a): la "longitud" o el número de exponentes que no desaparecen en un
- lo (a, b): (logaritmo de a en base b): Si a, b> 1 entonces el mayor x tal que b x | otro 0
- A continuación, la abreviatura x = def x 1 , ... x n ; se pueden aplicar subíndices si el significado lo requiere.
- #A: Una función φ definible explícitamente a partir de funciones Ψ y constantes q 1 , ... q n es primitiva recursiva en Ψ.
- #B: La suma finita Σ y
ψ ( x , y) y el producto Π y ψ ( x , y) son primitivos recursivos en ψ. - #C: Un predicado P obtenido al sustituir funciones χ 1 , ..., χ m por las respectivas variables de un predicado Q es primitivo recursivo en χ 1 , ..., χ m , Q.
- #D: Los siguientes predicados son primitivos recursivos en Q y R:
- NOT_Q ( x ).
- Q O R: Q ( x ) VR ( x ),
- Q Y R: Q ( x ) y R ( x ),
- Q IMPLICA R: Q ( x ) → R ( x )
- Q es equivalente a R: Q ( x ) ≡ R ( x )
- #E: Los siguientes predicados son primitivos recursivos en el predicado R:
- (Ey) y
R ( x , y) donde (Ey) y denota "existe al menos una y que es menor que z tal que" - (y) y
R ( x , y) donde (y) y denota "para todo y menor que z es cierto que" - μy y
R ( x , y). El operador μy y R ( x , y) es una forma acotada del llamado operador de minimización o mu : definido como "el valor mínimo de y menor que z tal que R ( x , y) es verdadero; o z si no existe tal valor ".
- (Ey) y
- #F: Definición por casos: La función así definida, donde Q 1 , ..., Q m son predicados mutuamente excluyentes (o "ψ ( x ) tendrá el valor dado por la primera cláusula que corresponda), es primitiva recursiva en φ 1 , ..., Q 1 , ... Q m :
- φ ( x ) =
- φ 1 ( x ) si Q 1 ( x ) es verdadero,
- . . . . . . . . . . . . . . . . . . .
- φ m ( x ) si Q m ( x ) es cierto
- φ m + 1 ( x ) de lo contrario
- φ ( x ) =
- #G: Si φ satisface la ecuación:
- φ (y, x ) = χ (y, COURSE-φ (y; x 2 , ... x n ), x 2 , ... x n entonces φ es primitivo recursivo en χ. El valor COURSE-φ (y ; x 2 an ) de la función de curso de valores codifica la secuencia de valores φ (0, x 2 an ), ..., φ (y-1, x 2 an ) de la función original.
Formas recursivas primitivas adicionales
Algunas formas adicionales de recursividad también definen funciones que de hecho son recursivas primitivas. Las definiciones en estas formas pueden ser más fáciles de encontrar o más naturales para leer o escribir. La recursividad de curso de valores define funciones recursivas primitivas. Algunas formas de recursividad mutua también definen funciones recursivas primitivas.
Las funciones que se pueden programar en el lenguaje de programación LOOP son exactamente las funciones recursivas primitivas. Esto da una caracterización diferente del poder de estas funciones. La principal limitación del lenguaje LOOP, en comparación con un lenguaje Turing completo , es que en el lenguaje LOOP el número de veces que se ejecutará cada bucle se especifica antes de que comience a ejecutarse.
Resultados de finitismo y consistencia
Las funciones recursivas primitivas están estrechamente relacionadas con el finitismo matemático y se utilizan en varios contextos de lógica matemática donde se desea un sistema particularmente constructivo. La aritmética recursiva primitiva (ARP), un sistema de axiomas formales para los números naturales y las funciones recursivas primitivas en ellos, se utiliza a menudo para este propósito.
PRA es mucho más débil que la aritmética de Peano , que no es un sistema finitista. Sin embargo, muchos resultados en teoría de números y en teoría de pruebas pueden demostrarse en PRA. Por ejemplo, el teorema de incompletitud de Gödel se puede formalizar en PRA, dando el siguiente teorema:
- Si T es una teoría de la aritmética que satisfacen ciertas hipótesis, la sentencia de Gödel G T , entonces ARP demuestra la implicación de Con ( T ) → G T .
De manera similar, muchos de los resultados sintácticos en la teoría de la prueba se pueden probar en PRA, lo que implica que hay funciones recursivas primitivas que llevan a cabo las correspondientes transformaciones sintácticas de las pruebas.
En la teoría de la prueba y la teoría de conjuntos , existe un interés en las pruebas de consistencia finitista , es decir, las pruebas de consistencia de que son finitísticamente aceptables. Tales una prueba establece que la consistencia de una teoría T implica la consistencia de una teoría S mediante la producción de una función recursiva primitiva que puede transformar cualquier prueba de una inconsistencia de S en una prueba de una inconsistencia de T . Una condición suficiente para que una prueba de coherencia sea finitista es la capacidad de formalizarla en PRA. Por ejemplo, muchos resultados de coherencia en la teoría de conjuntos que se obtienen forzando pueden reformularse como pruebas sintácticas que pueden formalizarse en PRA.
Historia
Las definiciones recursivas se habían utilizado más o menos formalmente en matemáticas antes, pero la construcción de la recursividad primitiva se remonta al teorema 126 de Richard Dedekind de su Was sind und was sollen die Zahlen? (1888). Este trabajo fue el primero en dar una prueba de que cierta construcción recursiva define una función única. [4] [5] [6]
La aritmética recursiva primitiva fue propuesta por primera vez por Thoralf Skolem [7] en 1923.
La terminología actual fue acuñada por Rózsa Péter (1934) después de que Ackermann demostrara en 1928 que la función que hoy lleva su nombre no era recursiva primitiva, hecho que motivó la necesidad de renombrar lo que hasta entonces se llamaba simplemente funciones recursivas. [5] [6]
Ver también
- Jerarquía de Grzegorczyk
- Recursión (informática)
- Primitivo funcional recursivo
- Doble recursividad
- Función de conjunto recursivo primitivo
- Función ordinal recursiva primitiva
Notas
- ^ Brainerd y Landweber, 1974
- ^ Kleene [1952 págs. 226-227]
- ^ Esto se sigue de los hechos de que las funciones de esta forma son las funciones recursivas primitivas de crecimiento más rápido, y que una función es recursiva primitiva si y sólo si su complejidad temporal está limitada por una función recursiva primitiva. Para el primero, véase Linz, Peter (2011), An Introduction to Formal Languages and Automata , Jones & Bartlett Publishers, p. 332, ISBN 9781449615529. Para este último, consulte Moore, Cristopher ; Mertens, Stephan (2011), La naturaleza de la computación , Oxford University Press, pág. 287, ISBN 9780191620805
- ^ Peter Smith (2013). Introducción a los teoremas de Gödel (2ª ed.). Prensa de la Universidad de Cambridge. págs. 98–99. ISBN 978-1-107-02284-3.
- ^ a b George Tourlakis (2003). Conferencias de Lógica y Teoría de Conjuntos: Volumen 1, Lógica Matemática . Prensa de la Universidad de Cambridge. pag. 129. ISBN 978-1-139-43942-8.
- ^ a b Rod Downey, ed. (2014). El legado de Turing: desarrollos a partir de las ideas de Turing en lógica . Prensa de la Universidad de Cambridge. pag. 474. ISBN 978-1-107-04348-0.
- ^ Thoralf Skolem (1923) "Los fundamentos de la aritmética elemental" en Jean van Heijenoort , traductor y ed. (1967) De Frege a Gödel: un libro de consulta en lógica matemática, 1879-1931 . Universidad de Harvard. Presione: 302-33.
Referencias
- Brainerd, WS, Landweber, LH (1974), Teoría de la Computación , Wiley, ISBN 0-471-09585-0
- Robert I. Soare , Conjuntos y grados recursivamente enumerables , Springer-Verlag, 1987. ISBN 0-387-15299-7
- Stephen Kleene (1952) Introducción a la metamatemática , North-Holland Publishing Company, Nueva York, 11ª reimpresión 1971: (notas de la 2ª edición añadidas en la 6ª reimpresión). En el Capítulo XI. Funciones recursivas generales §57
- George Boolos , John Burgess , Richard Jeffrey (2002), Computability and Logic: Fourth Edition , Cambridge University Press, Cambridge, Reino Unido. Cfr págs. 70-71.
- Robert I. Soare 1995 Computabilidad y recursividad http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
- Daniel Severin 2008, Funciones recursivas primitivas unarias , J. Symbolic Logic Volumen 73, Número 4, págs. 1122–1138 arXiv projecteuclid