Recursive set Guide, Meaning , Facts, Information and Description

In computability theory a set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether a given element belongs to the set or not. A more general class of sets are called recursively enumerable sets. For those sets the algorithm only terminates if the element belongs to the set otherwise it runs for an infinite amount of time.

Table of contents

1 Definition 2 Notes 3 Examples 4 See also

Definition

A subset A of the natural numbers is called recursive if there exists a total recursive function

with

In other words the set A is recursive iff the indicator function is computable

Notes

If A is a recursive set then the complement of A is a recursive set. If A and B are recursive sets then A ∩ B and A ∪ B are recursive sets. A set A is a recursive set iff A and the complement of A are recursively enumerable sets.

Examples

• the empty set
• the natural numbers
• every finite subset of the natural numbers
• the set of prime numbers

See also

• recursively enumerable set
• recursive function

This is an Article on Recursive set. Page Contains Information, Facts Details or Explanation Guide About Recursive set

	Web www.E-paranoids.com