4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.