|
|
|
|
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.
- 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 $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)
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 MSC: | 03D25 (Mathematical logic and foundations :: Computability and recursion theory :: Recursively enumerable sets and degrees) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
