Insiemi ricorsivi vs funzioni ricorsive

Question

Qual è la differenza tra un insieme ricorsivo e la funzione ricorsiva?

Answer 1

funzioni ricorsive e set ricorsive sono termini usati nella teoria della computabilità. Wikipedia li definisce come segue:

  

Un insieme di numeri naturali si dice che sia un insieme calcolabile (chiamato anche decidibile, ricorsivo, o Turing computabile degli insiemi) se esiste una macchina di Turing che, dato un numero n, si ferma con uscita 1 se n è set e arresta con uscita 0 se n non è nel set. Una funzione f dai numeri naturali per sé è una funzione calcolabile ricorsiva o (Turing) se esiste una macchina di Turing che, sull'ingresso n, arresta e restituisce in uscita f (n).

In questo contesto, una funzione ricorsiva non significa una funzione in un linguaggio di programmazione che si definisce. Qualsiasi funzione matematico che soddisfa i requisiti della definizione di cui sopra è una funzione ricorsiva, inclusi quelli banali come la funzione identità o la mappatura funzione tutti i numeri a 1 (cioè restituisce il numero 1 indipendentemente dall'ingresso).

Answer 2

Il significato di questi termini varia a seconda del contesto. Se stavamo discutendo li puramente dal punto di vista dei programmi di scrittura, allora insiemi ricorsivi non ha molto senso; tuttavia, potrebbe essere solo che ho incontrato ancora. Detto questo, funzioni ricorsive sono funzioni che si definiscono nella loro esecuzione. Il calcolo di un ^th numero di Fibonacci è il classico esempio che viene comunemente presentata:

/// <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);
 }
}

Detto questo, l'altro contesto per questi termini nel contesto di informatica e in particolare la teoria della computazione è quando si parla di linguaggi formali . In questo contesto, un insieme ricorsivo è definito come un insieme per il quale v'è un problema di appartenenza risolvibile. Ad esempio, sappiamo che l'insieme di tutte le numeri naturali ℕ è un insieme ricorsivo perché possiamo definire una funzione ricorsiva nel seguente modo:

  

Let f essere definito come una funzione in cui    f (x) = 1 se x ∈ ℕ e    f (x) = 0 se x ∉ ℕ

Il concetto di un insieme ricorsivo è importante per il concetto di computabilità perché conduce alla insieme ricorsivamente enumerabile , che è un linguaggio che può essere riconosciuto da un macchina di Turing (cioè Turing-riconoscibile ). Si tratta di lingue per le quali una macchina di Turing può o non può essere in grado di determinare se una data stringa è membro di una lingua, o in altre parole, la macchina può o accettare , Rifiuta o ciclo. Questo è in contrasto con una Turing-decidibile lingua per la quale una macchina entrerà in entrambi il accettare o rifiutare stato per una determinata stringa di input.

Questo dove il concetto di una funzione ricorsiva entra in gioco, come una funzione ricorsiva (o funzione ricorsiva totale) possono essere calcolate da una macchina di Turing e arresta per ogni ingresso. Dove come una funzione ricorsiva parziale può essere calcolato solo per una macchina di Turing senza alcuna garanzia riguardo al comportamento arresto. O nella sostanza la funzione ricorsiva è la controparte al set ricorsiva.

Quindi, per riportare le cose intorno alla tua domanda iniziale, nel contesto della teoria della computazione, un insieme ricorsivo è ciò che può essere generata (cioè enumerato) o di avere l'appartenenza testato da una funzione ricorsiva su una macchina di Turing.

Letture consigliate:

• M. Sipser - Introduzione alla teoria della computazione (Second Edition)
• J.E. Hopcroft, R. Motwani, JD Ullman - Introduzione alla teoria degli automi, Lingue, and Computation (Terza Edizione )
• H.R. Lewis, C.H. Papadimitriou - Elementi di teoria della computazione (Second Edition)
• F.D. Lewis - di Theoretical Computer Science (Digital testo)

Answer 3

Forse la domanda avrebbe dovuto essere "Perché la parola 'ricorsivo' usato per descrivere entrambi i set e le funzioni?"

Come Greg Hewgill ha sottolineato nel suo commento, la parola 'verde' può essere applicato alle mele e le auto, ma questo non implica un rapporto tra le mele e le auto.

Credo che la citazione da Wikipedia usa il termine 'ricorsivo' come sinonimo di 'calcolabile' -. Che noi, come i programmatori, sarebbe d'accordo con cautela, ma solo in determinati contesti