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
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

Recursively enumerable set

From Wikipedia, the free encyclopedia

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:

  • There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S.

Or, equivalently,

  • There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... . If necessary, this algorithm may run forever.

The first condition suggests why the term semidecidable is sometimes used; the second suggests why computably enumerable is used. The abbreviations r.e. and c.e. are often used, even in print, instead of the full phrase.

In computational complexity theory, the complexity class containing all recursively enumerable sets is RE. In recursion theory, the lattice of r.e. sets under inclusion is denoted .

YouTube Encyclopedic

  • 1/5
    Views:
    2 341
    33 726
    21 254
    1 284
    6 214
  • ✪ Recursively Enumerable - Intro to Theoretical Computer Science
  • ✪ Decidability and Undecidability
  • ✪ 57. RECURSIVE AND RECURSIVE ENUMERABLE LANGUAGES
  • ✪ Recognizability and Decidability - Georgia Tech - Computability, Complexity, Theory: Computability
  • ✪ An Undecidable Language - Georgia Tech - Computability, Complexity, Theory: Computability

Transcription

So the answer no is something we cannot obtain in finite time and that is why the Halting Problem is called semi-decidable, because we can kind of decide half of the answers and it's also called undecidable because we cannot output a clear yes or no after a finite amount of time. Why this nit-picking; what's the difference, you might ask. The interest of this, of course, is rather theoretic, but semi-decidable problems have a very interesting property called recursive enumerability. Now that sounds a bit strange; what does that mean? Recursive enumerability means that you can write a program that outputs all combinations of inputs and programs, and I seriously mean all combinations of inputs and programs that halt. So this program here cannot say for any input and program that this combination will not halt but it can output a complete list of inputs and programs that will halt, so let's have a look at this program, and of course, this program runs on infinitely, so it start off by defining a length called max length to be 0 and then it goes into an infinite loop, which is this one here, and what it does then is it increases max length by one each time it goes into this loop here, enumerates all programs of length at most max length. Now if you fix this max length here, there is a huge number of programs that have a length at most max length but it's finite; it's huge but finite, and the same goes for the inputs. So for all combinations of programs and inputs that are shorter than this value max length here, we run a simulation for exactly max length steps and if the program halts on the input after exactly max length steps, then we print the program, and we print the input. If it hasn't halted yet, don't care, throw it away, wait until the next loop.

Contents

Formal definition

A set S of natural numbers is called recursively enumerable if there is a partial recursive function whose domain is exactly S, meaning that the function is defined if and only if its input is a member of S.

Equivalent formulations

The following are all equivalent properties of a set S of natural numbers:

Semidecidability:
  • The set S is recursively enumerable. That is, S is the domain (co-range) of a partial recursive function.
  • There is a partial recursive function f such that:
Enumerability:
  • The set S is the range of a partial recursive function.
  • The set S is the range of a total recursive function or empty. If S is infinite, the function can be chosen to be injective.
  • The set S is the range of a primitive recursive function or empty. Even if S is infinite, repetition of values may be necessary in this case.
Diophantine:
  • There is a polynomial p with integer coefficients and variables x, a, b, c, d, e, f, g, h, i ranging over the natural numbers such that
(The number of bound variables in this definition is the best known so far; it might be that a lower number can be used to define all diophantine sets.)
  • There is a polynomial from the integers to the integers such that the set S contains exactly the non-negative numbers in its range.

The equivalence of semidecidability and enumerability can be obtained by the technique of dovetailing.

The Diophantine characterizations of a recursively enumerable set, while not as straightforward or intuitive as the first definitions, were found by Yuri Matiyasevich as part of the negative solution to Hilbert's Tenth Problem. Diophantine sets predate recursion theory and are therefore historically the first way to describe these sets (although this equivalence was only remarked more than three decades after the introduction of recursively enumerable sets).

Recursive enumeration of the set of all Turing machines halting on a fixed input: Simulate all Turing machines (enumerated on vertical axis) step by step (horizontal axis), using the shown diagonalization scheduling. If a machine terminates, print its number. This way, the number of each terminating machine is eventually printed. In the example, the algorithm prints "9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ..."
Recursive enumeration of the set of all Turing machines halting on a fixed input: Simulate all Turing machines (enumerated on vertical axis) step by step (horizontal axis), using the shown diagonalization scheduling. If a machine terminates, print its number. This way, the number of each terminating machine is eventually printed. In the example, the algorithm prints "9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ..."

Examples

  • Every recursive set is recursively enumerable, but it is not true that every recursively enumerable set is recursive. For recursive sets, the algorithm must also say if an input is not in the set – this is not required of recursively enumerable sets.
  • A recursively enumerable language is a recursively enumerable subset of a formal language.
  • The set of all provable sentences in an effectively presented axiomatic system is a recursively enumerable set.
  • Matiyasevich's theorem states that every recursively enumerable set is a Diophantine set (the converse is trivially true).
  • The simple sets are recursively enumerable but not recursive.
  • The creative sets are recursively enumerable but not recursive.
  • Any productive set is not recursively enumerable.
  • Given a Gödel numbering of the computable functions, the set (where is the Cantor pairing function and indicates is defined) is recursively enumerable (cf. picture for a fixed x). This set encodes the halting problem as it describes the input parameters for which each Turing machine halts.
  • Given a Gödel numbering of the computable functions, the set is recursively enumerable. This set encodes the problem of deciding a function value.
  • Given a partial function f from the natural numbers into the natural numbers, f is a partial recursive function if and only if the graph of f, that is, the set of all pairs such that f(x) is defined, is recursively enumerable.

Properties

If A and B are recursively enumerable sets then AB, AB and A × B (with the ordered pair of natural numbers mapped to a single natural number with the Cantor pairing function) are recursively enumerable sets. The preimage of a recursively enumerable set under a partial recursive function is a recursively enumerable set.

A set is recursively enumerable if and only if it is at level of the arithmetical hierarchy.

A set is called co-recursively enumerable or co-r.e. if its complement is recursively enumerable. Equivalently, a set is co-r.e. if and only if it is at level of the arithmetical hierarchy. The complexity class of co-recursively enumerable sets is denoted co-RE.

A set A is recursive (synonym: computable) if and only if both A and the complement of A are recursively enumerable. A set is recursive if and only if it is either the range of an increasing total recursive function or finite.

Some pairs of recursively enumerable sets are effectively separable and some are not.

Remarks

According to the Church–Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus a set S is recursively enumerable if and only if there is some algorithm which yields an enumeration of S. This cannot be taken as a formal definition, however, because the Church–Turing thesis is an informal conjecture rather than a formal axiom.

The definition of a recursively enumerable set as the domain of a partial function, rather than the range of a total recursive function, is common in contemporary texts. This choice is motivated by the fact that in generalized recursion theories, such as α-recursion theory, the definition corresponding to domains has been found to be more natural. Other texts use the definition in terms of enumerations, which is equivalent for recursively enumerable sets.

References

  • 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.
  • Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.
This page was last edited on 27 August 2019, at 06:11
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.