Relation and difference between recursively enumerable languages and Turing complete languages?

Question

From https://en.wikipedia.org/wiki/Recursively_enumerable_language

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.

From https://en.wikipedia.org/wiki/Turing_completeness

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.

1. 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?

2. What are their relations?

   For a language,

   • does being recursively enumerable imply being Turing complete?
   • Does being Turing complete imply being recursively enumerable?

Thanks.

Answer 1

Your confusion stems from overloaded terminology. The word "language" in "Turing complete languages" refers to a programming language, while in "recursively enumerable language", it refers to a formal language - that is, a set of strings formed over some alphabet.

So you're correct when you state:

the two concepts belong to two unrelated aspects of Turing machines

Both use Turing machines in their definition (at least in the most oft-used definition), but they are not the same class of mathematical object. This should clear up (2) for.

To clear up your other questions:

a recursively enumerable language a set of inputs to a Turing Machine for it to recognize

Yes, in fact, the recursively enumerable languages are also known as the Turing-recognizable languages. They are a strict superset of the decidable languages. For example, the halting problem is recognizable, but infamously undecidable.

a Turing complete language is the language provided by a Turing Machine or its equivalent?

Formally(-ish), a Turing complete language is one that can compute the same set of number-theoretic functions (i.e. functions N^k -> N) as a Turing machine.

Also, in the future, please try to ask one question per post. Thank you