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.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
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

Index set (computability)

From Wikipedia, the free encyclopedia

In computability theory, index sets describe classes of computable functions; specifically, they give all indices of functions in a certain class, according to a fixed Gödel numbering of partial computable functions.

Definition

Let be a computable enumeration of all partial computable functions, and be a computable enumeration of all c.e. sets.

Let be a class of partial computable functions. If then is the index set of . In general is an index set if for every with (i.e. they index the same function), we have . Intuitively, these are the sets of natural numbers that we describe only with reference to the functions they index.

Index sets and Rice's theorem

Most index sets are non-computable, aside from two trivial exceptions. This is stated in Rice's theorem:

Let be a class of partial computable functions with its index set . Then is computable if and only if is empty, or is all of .

Rice's theorem says "any nontrivial property of partial computable functions is undecidable".[1]

Completeness in the arithmetical hierarchy

Index sets provide many examples of sets which are complete at some level of the arithmetical hierarchy. Here, we say a set is -complete if, for every set , there is an m-reduction from to . -completeness is defined similarly. Here are some examples:[2]

  • is -complete.
  • is -complete.
  • is -complete.
  • is -complete.
  • is -complete.
  • is -complete.
  • is -complete.
  • is -complete.
  • is -complete, where is the halting problem.

Empirically, if the "most obvious" definition of a set is [resp. ], we can usually show that is -complete [resp. -complete].

Notes

  1. ^ Odifreddi, P. G. Classical Recursion Theory, Volume 1.; page 151
  2. ^ Soare, Robert I. (2016), "Turing Reducibility", Turing Computability, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 51–78, ISBN 978-3-642-31932-7, retrieved 2021-04-21

References

  • Odifreddi, P. G. (1992). Classical Recursion Theory, Volume 1. Elsevier. p. 668. ISBN 0-444-89483-7.
  • Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. p. 482. ISBN 0-262-68052-1.
This page was last edited on 26 April 2021, at 00:58
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.