a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.
a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine.
So both recursively enumerable languages and Turing complete languages are defined in terms of Turing Machines.
What are the fundamental differences between recursively enumerable languages and Turing complete languages?
For example, is it correct that
- a recursively enumerable language a set of inputs to a Turing Machine for it to recognize, while
- a Turing complete language is the language provided by a Turing Machine or its equivalent?
So do the two concepts belong to two unrelated aspects of Turing machines?
What are their relations?
For a language,
- does being recursively enumerable imply being Turing complete?
- Does being Turing complete imply being recursively enumerable?