To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

From Wikipedia, the free encyclopedia

In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not.

A set which is not computable is called noncomputable or undecidable.

A more general class of sets than the decidable ones consists of the recursively enumerable sets, also called semidecidable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number is in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set.

YouTube Encyclopedic

  • 1/3
    Views:
    25 150
    1 667
    1 145
  • ✪ Mod-06 Lec-31 RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM
  • ✪ Recursively Enumerable - Intro to Theoretical Computer Science
  • ✪ Write A Recursive Definition Of The Function

Transcription

Contents

Formal definition

A subset S of the natural numbers is called recursive if there exists a total computable function f such that f(x) = 1 if xS and f(x) = 0 if xS. In other words, the set S is recursive if and only if the indicator function 1S is computable.

Examples

Properties

If A is a recursive set then the complement of A is a recursive set. If A and B are recursive sets then AB, AB and the image of A × B under the Cantor pairing function are recursive sets.

A set A is a recursive set if and only if A and the complement of A are both recursively enumerable sets. The preimage of a recursive set under a total computable function is a recursive set. The image of a computable set under a total computable bijection is computable.

A set is recursive if and only if it is at level Δ0
1
of the arithmetical hierarchy.

A set is recursive if and only if it is either the range of a nondecreasing total computable function or the empty set. The image of a computable set under a nondecreasing total computable function is computable.

References

  • Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
  • Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
  • Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7

External links

This page was last edited on 10 August 2019, at 17:28
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.