recursive set
recursive set A subset A of a set B is said to be recursive, relative to B, if there is an algorithm or effective procedure that, given an element b in B, will output “yes” if b is an element of A and “no” if b is not an element of A. The set A is thus also said to be decidable or computable.
Strictly speaking the sets A and B should be sets of natural numbers, and the algorithm is a definition of the total recursive function that is the characteristic function of A in B. The concept and terminology is transferred to other data sets using a Gödel numbering.
Post's theorem says that a set A is recursive iff A and B–A are recursively enumerable.
Strictly speaking the sets A and B should be sets of natural numbers, and the algorithm is a definition of the total recursive function that is the characteristic function of A in B. The concept and terminology is transferred to other data sets using a Gödel numbering.
Post's theorem says that a set A is recursive iff A and B–A are recursively enumerable.
More From encyclopedia.com
Set Theory , A set is a collection of things. A set can consist of real or literal numbers (such as 1, 2, 3, 4 or a, b, c, d) or of objects (such as baseballs or… Boolean Algebra , Boolean algebra is often referred to as the algebra of logic, because the English mathematician George Boole, who is largely responsible for its begi… Set (seth) , set1 / set/ • v. (set·ting ; past set ) 1. [tr.] put, lay, or stand (something) in a specified place or position: Dana set the mug of tea down | Cath… Georg Cantor , Cantor, Georg
Cantor, Georg
mathematics, set theory.
Cantor’s father, Georg Waldemar Cantor, was a successful and cosmopolitan merchant. His extant l… Reset , re·set / rēˈset/ • v. (-set·ting ; past and past part. -set ) [tr.] set again or differently: I must reset the alarm. ∎ Electr. cause (a binary devic… Map , Map
A map, or mapping, is a rule, often expressed as an equation, that specifies a particular element of one set for each element of another set. To…
You Might Also Like
NEARBY TERMS
recursive set