PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
recursively enumerable (Definition)

For a language $L$ , TFAE:

  • There exists a Turing machine $f$ such that $\forall x.(x\in L) \iff \mbox{the computation $ f(x)$ terminates}$ .
  • There exists a total recursive function $f:\Nats\to L$ which is onto.
  • There exists a total recursive function $f:\Nats\to L$ which is one-to-one and onto.

A language $L$ fulfilling any (and therefore all) of the above conditions is called recursively enumerable.

Examples

  1. Any recursive language.
  2. The set of encodings of Turing machines which halt when given no input.
  3. The set of encodings of theorems of Peano arithmetic.
  4. The set of integers $n$ for which the hailstone sequence starting at $n$ reaches 1. (We don't know if this set is recursive, or even if it is $\Nats$ ; but a trivial program shows it is recursively enumerable.)




"recursively enumerable" is owned by ariels.
(view preamble | get metadata)

View style:

See Also: halting problem, Turing computable

Other names:  semi-recursive
Also defines:  semi-recursive, recursively enumerable function
Log in to rate this entry.
(view current ratings)

Cross-references: even, recursive, sequence, integers, Peano arithmetic, theorems, recursive language, one-to-one, onto, recursive function, Turing machine, TFAE, language
There are 8 references to this entry.

This is version 3 of recursively enumerable, born on 2002-06-05, modified 2002-06-05.
Object id is 3045, canonical name is RecursivelyEnumerable.
Accessed 8918 times total.

Classification:
AMS MSC03D25 (Mathematical logic and foundations :: Computability and recursion theory :: Recursively enumerable sets and degrees)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)