Recursive Sets vs Recursive Functions

computer-science, formal-languages, theory

Solution

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).

Problem

Original source