请输入您要查询的字词:

 

单词 RecursiveSet
释义

recursive set


A subset S of the natural numbersMathworldPlanetmath is said to be recursive if its characteristic functionMathworldPlanetmathPlanetmathPlanetmath

χS(x):={1 if xS0 if x-S

is recursive (computable). In other words, there is an algorithmMathworldPlanetmath (via Turing machineMathworldPlanetmath for example) that determines whether an element is in S or not in S.

More generally, a subset Sn is recursive if its characteristic function fS is recursive.

A recursive setMathworldPlanetmath 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 numbersMathworldPlanetmath, the set of pairs (a,b) where a divides b, and the set of prime numbersMathworldPlanetmath. In the last example, one may use the Sieve of EratosthenesMathworldPlanetmathPlanetmath as an algorithm to determine the primality of an integer.

A set S is recursively enumerable if the partial functionMathworldPlanetmath

f(x):={1 if xSundefined if x-S

is computable. In other words, there is an algorithm that halts (and returns 1) only when an element in S 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 n. Below are two examples:

    • Since can be effectively embedded in , so the notion of recursive sets be extended to subsets of .

    • Since every finite setMathworldPlanetmath Σ can be encoded by the natural numbers, we can define a recursive language over Σ to be a subset LΣ* such that L, when encoded by the natural numbers, is a recursive set. Equivalently, L is recursive iff there is a Turing machine that decides L (accepts L and rejects Σ*-L).

  • Similarly, recursive enumerability can be defined on languagesPlanetmathPlanetmath: a language L over Σ is recursively enumerable if its encoding by the natural numbers is a recursively enumerable set. This is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to saying that L is accepted by a Turing machine.

  • Using the above definition, one can define a recursive predicate or a recursively enumerable predicate φ(x) according to whether {xφ(x)} is a recursive or recursively enumerable set respectively.

Titlerecursive set
Canonical nameRecursiveSet
Date of creation2013-03-22 17:34:52
Last modified on2013-03-22 17:34:52
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id16
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 03B25
Classificationmsc 03D20
Synonymdecidable set
Synonymcomputable set
Synonymdecidable predicate
Synonymcomputable predicate
Definesrecursively enumerable set
Definesrecursive predicate
Definesrecursively enumerable predicate
Definesrecursive language

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 16:16:20