Conjuntos recursivos vs Funções Recursivas

Question

O que é a diferença entre um conjunto recursivo e função recursiva?

Answer 1

funções recursivas e conjuntos recursivos são termos usados ??na teoria da computabilidade. Wikipedia define-los da seguinte forma:

Um conjunto de números naturais é dito ser um conjunto calculável (também chamado um decidíveis, recursiva, ou Turing conjunto calculável) se existe uma máquina de Turing que, dado um número n, paradas com saída 1 se n for no conjunto e pára a saída com 0 se n não está no conjunto. Uma função F a partir dos números naturais para si é um recursiva ou (Turing) função calculável se existe uma máquina de Turing que, na entrada n, pára e regressa saída f (n).

Neste contexto, uma função recursiva não significa uma função em uma linguagem de programação que se chama. Qualquer matemático função que satisfaz os requisitos da definição acima é uma função recursiva, incluindo aqueles triviais tais como a função de identidade ou a função de mapeamento de todos os números para um (isto é, retorna o número 1, independentemente de entrada).

Answer 2

O significado desses termos varia de acordo com o seu contexto. Se estávamos discutindo-los puramente do ponto de vista de escrever programas, em seguida, conjuntos recursivos não faz muito sentido; no entanto, pode ser apenas que eu encontrei ainda. Dito isto, funções recursivas são funções que chamam a si mesmos em sua execução. O cálculo de um ^th número de Fibonacci é o exemplo clássico que é comumente apresentada:

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

Dito isto, o outro contexto para estes termos no contexto da ciência da computação e, especificamente, a teoria da computação é quando se fala de linguagens formais . Neste contexto, a conjunto recursivo é definido como um conjunto para os quais existe um problema de adesão solúvel. Por exemplo, sabemos que o conjunto dos números naturais todos N é um conjunto recursivo porque podemos definir uma função recursiva como segue:

Vamos f ser definida como uma função onde f (x) = 1 se x ? N e f (x) = 0 se x ? N

O conceito de um conjunto recursivo é importante para o conceito de computabilidade, pois leva ao conjuntos recursivamente enumeráveis ?? que é uma linguagem que pode ser reconhecido por um máquina de Turing (ou seja, Turing-reconhecível ). Estes são idiomas para os quais uma máquina de Turing pode ou não ser capaz de determinar se uma determinada string é um membro de uma língua, ou em outras palavras, a máquina pode ou aceitar , rejeitar ou loop. Isto está em contraste com a Turing-decidable linguagem para que a máquina entrará em tanto o aceitar ou rejeitar estado para uma determinada cadeia de entrada.

Este, onde o conceito de um função recursiva vem em jogo, como uma função recursiva (ou função recursiva total) pode ser calculado por uma máquina de Turing e paradas para cada entrada. Onde como uma função recursiva parcial só pode ser calculado por uma máquina de Turing com nenhuma garantia em relação ao comportamento de parada. Ou na sua essência a função recursiva é a contrapartida para o conjunto recursivo.

Assim, para trazer as coisas de volta em torno à sua pergunta original, no contexto da teoria da computação, um conjunto recursivo é o que pode ser gerado (ou seja enumerado) ou que tenham filiação testado por uma função recursiva em uma máquina de Turing.

Leitura adicional:

• M. Sipser - Introdução à Teoria da Computação (Segunda Edição)
• J.E.. Hopcroft, R. Motwani, JD Ullman - Introdução à Teoria dos Autômatos, Linguagens e Computação (Terceira Edição )
• H.R.. Lewis, C. H. Papadimitriou - Elementos de Teoria da Computação (Segunda Edição)
• F.D. Lewis - Essentials de Ciência da Computação Teórica (Texto Digital)

Answer 3

Talvez a pergunta deveria ter sido "Porque é que a palavra 'recursiva' usado para descrever ambos os conjuntos e funções?"

Como Greg Hewgill apontou em seu comentário, a palavra 'verde' pode ser aplicado a maçãs e carros, mas isso não implica uma relação entre maçãs e carros.

Eu acho que a citação de Wikipedia usa o termo 'recursivo' como sinônimo de 'computável' -. Que nós, como programadores, que cautelosamente concordar, mas apenas em certos contextos