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?
Best Answer
Godel, in his incompleteness theorems, uses the two notions: Strong Representability and Weak Representability. Taken from link we have the following:
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.