Recursive Sets vs Recursive Functions

Question

What s the difference between a recursive set and recursive function?

Answer 1

Perhaps the question should have been "Why is the word 'recursive' used to describe both sets and functions?"

As Greg Hewgill pointed out in his comment, the word 'green' can be applied to apples and cars, but this does not imply a relationship between apples and cars.

I think the quote from Wikipedia uses the term 'recursive' as a synonym for 'computable' — which we, as programmers, would cautiously agree with, but only in certain contexts.

Answer 2

Recursive functions and recursive sets are terms used in computability theory. Wikipedia defines them as follows:

A set of natural numbers is said to be a computable set (also called a decidable, recursive, or Turing computable set) if there is a Turing machine that, given a number n, halts with output 1 if n is in the set and halts with output 0 if n is not in the set. A function f from the natural numbers to themselves is a recursive or (Turing) computable function if there is a Turing machine that, on input n, halts and returns output f(n).

In this context, a recursive function does not mean a function in a programming language that calls itself. Any mathematical function that meets the requirements of the definition above is a recursive function, including trivial ones such as the identity function or the function mapping all numbers to 1 (i.e. returns the number 1 regardless of input).

Answer 3

The meaning of these terms varies depending upon your context. If we were discussing them purely from the standpoint of writing programs then recursive sets don't make much sense; however, it might just be that I have encountered it yet. That said, recursive functions are functions that call themselves in their execution. The calculation of a n^th Fibonacci number is the classic example that is commonly presented:

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

That said, the other context for these terms in the context of computer science and specifically the theory of computation is when discussing of formal languages. In this context, a recursive set is defined to be a set for which there is a solvable membership problem. For example, we know that the set of all natural numbers ℕ is a recursive set because we can define a recursive function as follows:

Let f be defined as a function where f(x) = 1 if x ∈ ℕ and f(x) = 0 if x ∉ ℕ

The concept of a recursive set is important for the concept of computability because it leads to the recursively enumerable set which is a language that can be recognized by a Turing machine (i.e. Turing-recognizable). These are languages for which a Turing machine may or may not be able to determine if a given string is a member of a language, or in other words, the machine may either accept, reject, or loop. This is in contrast to a Turing-decidable language for which a the machine will enter into either the accept or reject state for a given input string.

This where the concept of a recursive function comes in play, as a recursive function (or total recursive function) can be computed by a Turing machine and halts for every input. Where as a partial recursive function can only be computed for a Turing machine with no guarantee in regard to halting behavior. Or in essence the recursive function is the counterpart to the recursive set.

So to bring things back around to your original question, in the context of the theory of computation, a recursive set is what can be generated (i.e. enumerated) or have membership tested by a recursive function on a Turing machine.

Further Reading:

• M. Sipser - Introduction to the Theory of Computation (Second Edition)
• J.E. Hopcroft, R. Motwani, J.D. Ullman - Introduction to Automata Theory, Languages, and Computation (Third Edition)
• H.R. Lewis, C.H. Papadimitriou - Elements of the Theory of Computation (Second Edition)
• F.D. Lewis - Essentials of Theoretical Computer Science (Digital Text)

Answer 4

A primitive recursive set is a subset of N whose characteristic function (that tells when something is in

it and when it is not) is a primitive recursive function from N to {0,1}.