Entiendo que "recursivo" son aquellos que pueden ser totalmente decidido por un algoritmo, mientras que "recurrentemente enumerable" conjuntos pueden ser incluidas por un algoritmo (pero no necesariamente decidido). Tengo curiosidad, por qué aparece la palabra "recursivo" en su nombre. ¿Qué tiene que ver con las funciones que se hacen llaman el concepto de decidability/reconocimiento?
Respuestas
¿Demasiados anuncios?
Hay una historia aquí. En versión miniatura, en la década de 1930 en los diversos intentos que se hacen para caracterizar formalmente la intuitivamente computable funciones numéricas, y relatedly la eficacia decidable conjuntos de números (es decir, aquellos cuya composición puede ser decidido por una función computable). Así encontramos como varios oficiales de cuentas de la computabilidad de la Iglesia la idea de $\lambda$-computabilidad de Turing computabilidad, Herbrand-Gödel computabilidad, y Gödel y Kleene $\mu$-recursividad (y más!). De estos, es en esta última definición formal de la computabilidad, donde la noción de recursividad en el sentido de una función se llama a sí mismo de forma centralizada características.
Ahora como una cuestión de técnica, de hecho, el $\lambda$-computable de la función, la de Turing-computable funciones, la Herbrand-Gödel funciones computables, y el ($\mu$)-funciones recursivas va a ser la misma clase de funciones. Y por diversas razones, el término preferido para esta clase de funciones se convirtió en "recursivo".
El técnico hecho de que todos estos intentos (y otros más tarde) para caracterizar la forma intuitiva funciones computables convergen en las funciones recursivas conduce a la tesis de Church-Turing que las funciones computables en el sentido intuitivo sólo son estas funciones recursivas (y la decidable conjuntos de números son los conjuntos recursivos, es decir, aquellos con una característica recursiva de la función).
Yo no lo mismo decir que "computable" significa "recursiva" (ni yo recomiendo una lingüística de la reforma a este efecto). Más bien, yo lo pondría así: es un descubrimiento que la idea intuitiva de un algorítmicamente función computable (vestida un poco) selecciona la clase de las funciones recursivas.
iturki
Puntos
106
Hoy en día en el contexto de la rama de las matemáticas llamada teoría de la recursividad o la teoría de la computabilidad, el término recursivo y computable, significan la misma cosa. El término decidable también significan lo mismo, pero más a menudo se utiliza en el contexto de la lógica de las teorías o en los libros de texto más centrado en la ciencia de la computación. Todos estos términos significa que hay un procedimiento eficaz para determinar la pertenencia de algunos de los conjuntos. Eficaz formalmente medio aceptado por una Máquina de Turing, $\mu$-función recursiva, registro ilimitado de la máquina, $\lambda$ cálculo, etc.
Los términos computable enumerable, recursivamente enumerable, reconocible todos significan lo mismo. Ellos son el dominio de los algoritmos, el rango de un total de algoritmo, el $\Sigma_1^0$ definibles subconjuntos de a $\omega$, etc.
Como he mencionado anteriormente, existen varios formal del modelo de cálculo que definen el concepto de ser computable (decidable, recursivo). Sospecho que el nombre de "recursividad" proviene de uno de los primeros método de cálculo. Creo Kleene demostrado que muchos de los teoremas fundamentales de la teoría de la computabilidad el uso de primitivas de funciones recursivas y el $\mu$-funciones recursivas. Posiblemente esto es donde el término de la recursión.
Soare se sostiene en la década de 1990 que el nombre del campo que se llama la Teoría de la Recursividad debe ser llamada la Teoría de la Computabilidad. Los siguientes documentos describen la historia de el nombre de "recursividad" y "computabilidad" y por qué cree que la computabilidad es más apropiado.
http://www.people.cs.uchicago.edu/~soare/Historia/informática.pdf http://www.people.cs.uchicago.edu/~soare/Historia/siena.pdf
Michael Hardy
Puntos
128804
Citando un comentario por el cartel original: "Es 'recursividad' una palabra en ciencias de la computación que tiene dos significados ("computable" y "función que se llama a sí mismo")? O son los significados de alguna manera relacionados?"
Sí, que están relacionados, pero que podría razonablemente gusta la manera en que están relacionados.
Que funciones son computables?
Entre las que se encuentran
- el cero de la función;
- proyección funciones: $p_k(x_1,\ldots,x_k,\ldots,x_n) = x_k$;
- la función sucesor: $s(x)=x+1$ (si las palabras de un alfabeto, en lugar de los números, son los argumentos de estas funciones, entonces existe una función sucesor para cada letra del alfabeto --- por ejemplo, el correspondiente a la "c" añade que la letra al final de la entrada de la palabra);
- composiciones de funciones computables;
- funciones definidas por recursión (llamar): $f(x_1,\ldots,x_k+1,\ldots,x_n) = \text{some expression involving }f(x_1,\ldots,x_k,\ldots,x_n)$;
- funciones definidas a partir de otras funciones de minimización: $f(x_1,\ldots,x_n) = \min\{y : g(y,x_1,\ldots,x_n)=0\}$.
. . . y no otros, si la Iglesia--Turing tesis es correcta. Por lo tanto las funciones definidas por recursión son precisamente las funciones computables.
Minimización significa que algunas funciones computables no están en todas partes definidas, y no sabemos si el algoritmo se ejecutará siempre porque la función no está definida. Usted puede estar buscando el menor número $>2$ que no es la suma de dos números primos, o el número más pequeño $>1$ que aparece en al menos nueve veces en el triángulo de Pascal (la existencia de cualquiera de las dos es una pregunta abierta). Sin incluida la minimización de obtener una clase de funciones que pueden ser mostrados por una diagonal argumento para no incluir todas las funciones computables.
Hay otros aparentemente muy diferentes caracterizaciones de la computabilidad. Cada general-lenguaje de programación de propósito es tal caracterización. Pero simple caracterizaciones como la de arriba, que es en efecto un simple lenguaje de programación, son útiles, no para la escritura de programas, pero para explorar la frontera entre lo que es y lo que no es computable.
Arctictern
Puntos
85
¿Qué significa el concepto de decidability/reconocimiento tiene que ver con las funciones que se llaman a sí mismos?
La primitiva recursiva funciones están estrechamente relacionadas con las funciones que se llaman a sí mismos. Para el general o $\mu$-función recursiva, y adicionales de minimización de la operación está permitido. Esta minimización de la operación no siempre es posible definir una función, por lo tanto conduce a funciones parciales.
Sin embargo, tengo que admitir que la función de Ackermann no es primitiva recursiva (es un $\mu$-recursiva total de la función), siendo su definición se parece a una función que se llama a sí misma. De modo que la relación entre el $\mu$-recursivo (total) funciones y funciones que se llaman a sí mismos es más profundo que un simple nombre inapropiado.
