PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
create new user
forget your password?
Main Menu
recursively enumerable (Definition)

For a language $ L$, TFAE:

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


  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 $ \mathbb{N}$; but a trivial program shows it is recursively enumerable.)

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

View style:

See Also: halting problem, Turing computable

Other names:  semi-recursive
Also defines:  semi-recursive, recursively enumerable function

Cross-references: even, sequence, integers, Peano arithmetic, recursive, one-to-one, onto, recursive function, Turing machine, TFAE, language
There are 2 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 5310 times total.

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

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

No messages.

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