Conjuntos recursivas vs funciones recursivas

Question

¿Cuál es la diferencia entre un conjunto recursivo y la función recursiva?

Answer 1

Las funciones recursivas y conjuntos recursivos son términos utilizados en teoría de la computabilidad. Wikipedia lo define de la siguiente manera:

  

un conjunto de números naturales se dice que es un conjunto computable (también llamado un decidable, recurrente, o Turing conjunto computable) si hay una máquina de Turing que, dado un número n, se detiene con la salida 1 si n es en el establecer y detiene con la salida 0 si n no está en el conjunto. Una función f de los números naturales a sí mismos es una función computable recursiva o (Turing) si hay una máquina de Turing que, en la entrada n, se detiene y vuelve f de salida (n).

En este contexto, una función recursiva no significa una función en un lenguaje de programación que se llama. Cualquier función matemático que cumpla con los requisitos de la definición anterior es una función recursiva, incluyendo los triviales, como la función de la identidad o la correlación de funciones todos los números a 1 (es decir, devuelve el número 1 independientemente de la entrada).

Answer 2

El significado de estos términos varía dependiendo de su contexto. Si estábamos hablando de ellas puramente desde el punto de vista de la escritura de programas a continuación, conjuntos recursivos no tiene mucho sentido; Sin embargo, puede que solo sea que he encontrado todavía. Dicho esto, funciones recursivas son funciones que llaman a sí mismos en su ejecución. El cálculo de un ^º número de Fibonacci es el ejemplo clásico que se presenta comúnmente:

/// <summary>A C# implementation of a function to return the nth Fibonacci number.</summary>
private static int Fibonacci(int n) {
 if (n <= 2) {
  return 1;
 } else {
  return Fibonacci(n - 1) + Fibonacci(n - 2);
 }
}

Dicho esto, el otro contexto para estos términos en el contexto de la informática y, específicamente, la teoría de la computación es cuando se habla de lenguajes formales. En este contexto, conjunto recursivo se define un ser un conjunto para el cual no es un problema solucionable membresía. Por ejemplo, sabemos que el conjunto de todos los números naturales ℕ es un conjunto recursivo ya que podemos definir una función recursiva como sigue:

  

Vamos a f puede definir como una función donde    f (x) = 1 si x ∈ ℕ y    f (x) = 0 si x ∉ ℕ

El concepto de un conjunto recursivo es importante para el concepto de computabilidad, ya que conduce a la conjunto recursivamente numerable que es un lenguaje que puede ser reconocida por un Turing máquina (es decir, Turing-reconocible ). Estos son idiomas para que una máquina de Turing puede o no ser capaz de determinar si una determinada cadena es un miembro de una lengua, o en otras palabras, la máquina puede o bien confirmar , Rechazar o bucle. Esto es en contraste a una Turing-decidible un idioma para el que la máquina va a entrar en cualquiera de los confirmar o rechazar estado de una cadena de entrada dada.

Este donde el concepto de un función recursiva viene en juego, como una función recursiva (o función recursiva total) se pueden calcular por una máquina de Turing y se detiene para cada entrada. Si, una función recursiva parcial sólo puede ser calculado para una máquina de Turing con ninguna garantía en lo que se refiere al comportamiento detención. O en lo esencial la función recursiva es la contrapartida del conjunto recursivo.

Así que para que las cosas vuelvan en torno a su pregunta original, en el contexto de la teoría de la computación, un conjunto recursivo es lo que se puede generar a prueba por una función recursiva en una máquina de Turing (es decir enumerado) o tienen afiliación.

Lectura adicional:

• M. Sipser - Introducción a la Teoría de la Computación (Segunda Edición)
• J.E.. Hopcroft, R. Motwani, JD Ullman - Introducción a la Teoría de Autómatas, Lenguajes y Computación (Tercera Edición )
• H.R. Lewis, C. H. Papadimitriou - Elementos de la Teoría de la Computación (Segunda Edición)
• F.D. Lewis - de Ciencias de la Computación Teórica (texto digital)

Answer 3

Tal vez la pregunta debería haber sido "¿Por qué la palabra 'recursivo' utilizado para describir ambos conjuntos y funciones?"

Como Greg Hewgill señaló en su comentario, la palabra 'verde' se puede aplicar a las manzanas y los coches, pero esto no implica una relación entre las manzanas y coches.

Creo que la cita de Wikipedia utiliza el término 'recursiva' como sinónimo de 'computable' -. Que, como programadores, estaríamos de acuerdo con cautela, pero sólo en ciertos contextos