Whats the connection between Turing machine and First order logic?

Question

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine).

Which looks very similar to the Δ elemantary class which has the property that if a model $M$ and its complement are Δ elementary class then $M$ is elementary.

So i am curious as to how do some of the elementary and Δ elementary classes relate to recursively enumerable and recursive languages?

For example: Connected graphs are not elementary class. How does that problem translate to turing machine? (As i can write a halting program to find whether a graph is connected or not).

EDIT: Seems like decidability of First-order theories has got lot to do with the recursive-enumerability of the Language (Godel's theorem). I instinctively feel that there is some more relation to Δ elementary and recursively enumerable languages and i still dont completely get it. Or does a elementary class decide the 'decidability' of the theory?

Answer 1

Godel, in his incompleteness theorems, uses the two notions: Strong Representability and Weak Representability. Taken from link we have the following:

A set S of natural numbers is strongly representable in F if there is a formula A(x) of the language of F with one free variable x such that for every natural number n:

n ∈ S ⇒ F ⊢ A(n);
n ∉ S ⇒ F ⊢ ¬A(n),

A set S of natural numbers is weakly representable in F if there is a formula A(x) of the language of F such that for every natural number n:

n ∈ S ⇔ F ⊢ A(n).

So the idea is given a first order language F, the above to definitions categorize certain sets.

The connection to Turing machines, or recursion theory in general, is as follows: The strongly representable sets of first order language F are identical with the recursive sets, while the weakly representable sets of first order language F are identical with the recursively enumerable sets.