recursive set
A subset of the natural numbers is said to be recursive if its characteristic function
is recursive (computable). In other words, there is an algorithm (via Turing machine for example) that determines whether an element is in or not in .
More generally, a subset is recursive if its characteristic function is recursive.
A recursive set is also known as a decidable set or a computable set.
Examples of recursive sets are finite subset of , the set itself, the set of even integers, the set of Fibonacci numbers, the set of pairs where divides , and the set of prime numbers. In the last example, one may use the Sieve of Eratosthenes as an algorithm to determine the primality of an integer.
A set is recursively enumerable if the partial function
is computable. In other words, there is an algorithm that halts (and returns ) only when an element in is used as an input.
Remarks
-
•
A special case of a recursive set is that of a primitive recursive set. A set is primitive recursive if its characteristic function is primitive recursive (http://planetmath.org/PrimitiveRecursive). All of the examples cited above are primitive recursive.
-
•
On the other hand, one can broaden the scope of recursiveness to sets which are not necessarily subsets of . Below are two examples:
-
–
Since can be effectively embedded in , so the notion of recursive sets be extended to subsets of .
-
–
Since every finite set can be encoded by the natural numbers, we can define a recursive language over to be a subset such that , when encoded by the natural numbers, is a recursive set. Equivalently, is recursive iff there is a Turing machine that decides (accepts and rejects ).
-
–
-
•
Similarly, recursive enumerability can be defined on languages: a language over is recursively enumerable if its encoding by the natural numbers is a recursively enumerable set. This is equivalent to saying that is accepted by a Turing machine.
-
•
Using the above definition, one can define a recursive predicate or a recursively enumerable predicate according to whether is a recursive or recursively enumerable set respectively.
Title | recursive set |
Canonical name | RecursiveSet |
Date of creation | 2013-03-22 17:34:52 |
Last modified on | 2013-03-22 17:34:52 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 16 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03B25 |
Classification | msc 03D20 |
Synonym | decidable set |
Synonym | computable set |
Synonym | decidable predicate |
Synonym | computable predicate |
Defines | recursively enumerable set |
Defines | recursive predicate |
Defines | recursively enumerable predicate |
Defines | recursive language |