PlanetMath: recursively enumerable

PlanetMath

(more info)

Math for the people, by the people.

Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS

Login

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Owner confidence rating: Low

Entry average rating: No information on entry rating

recursively enumerable

(Definition)

For a language , TFAE:

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

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

Examples

Any recursive language.
The set of encodings of Turing machines which halt when given no input.
The set of encodings of theorems of Peano arithmetic.
The set of integers for which the hailstone sequence starting at 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)

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, recursive language, one-to-one, onto, recursive function, Turing machine, TFAE, language
There are 4 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 7117 times total.

Classification:

03D25 (Mathematical logic and foundations :: Computability and recursion theory :: Recursively enumerable sets and degrees)

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

No messages.

Interact

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