Is turing completeness related to recursive enumerable languages?

Question

I recently came across this term "Turing complete" in my study of morphogenesis models. When I looked up, it said that a turing complete machine can simulate a universal turing machine.

When I looked up for its relationship with recursive enumerable languages, I couldn't find anything substantial.

My question is:

Will a turing computable machine always accept recursive enumerable languages?

Thanks in advance!

Answer 1

A language $L$ is computable if there is a Turing machine $M$ such that:

1. If $x \in L$ then $M$ halts on input $x$ with "YES" written on the output tape.
2. If $x \notin L$ then $M$ halts on input $x$ with "NO" written on the output tape.

A language $L$ is recursively enumerable if there is a Turing machine $M$ such that:

1. If $x \in L$ then $M$ halts on input $x$.
2. If $x \notin L$ then $M$ doesn't halt on input $x$.

As an example, consider the language HALT of all Turing machines that halt on the empty input. HALT is recursively enumerable, since given a Turing machine $M$, we can simulate it on the empty input. However, HALT is not decidable, as Turing showed using diagonalization.

Turing completeness is an informal concept (though it can probably be formalized). According tot he Wikipedia definition, a computing system is Turing-complete if:

1. Everything that can be computed by the system is computable (on a Turing machine).
2. Every computable language can be computed by the system.

However, we could just as well define Turing completeness with respect to recursive enumerability. The two definitions are probably equivalent for all reasonable computing systems.