Qfyilyi

I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this thought:

If I had a language A that is recursive for some Turing Machine, TM(A), would it be possible to design another TM, TM(A2), where you add in a feature that instead makes TM(A2) loop for one or more words in A?

Now, A is no longer recursive.

This seems to be intuitively obvious for at least some examples (though my example is with a very simple language). Say A = {1}, and TM(A) is a program that just says:

'if (x=1)
{return true}'

For TM(A), A is accepted.

Now, let TM(A2) be a program that says 'while (x>_1) {x+=1}', and so now A causes TM(A2) to loop forever.

Granted that this example may unbenkownst to me be too simple to prove a real point, but if the above holds, then yes, languages can be of 'different types' depending on their context.

However, in none of the literature I've seen has this been written to be the case? If a language is recursively enumerable in one given example, it's recursively enumerable altogether - that seems to be the description of how it works.

To combat this confusion then, and given also that a language type in the Chomsky hierarchy is a subset of the types above it in the hierarchy, would this be a correct definition of the 'type of a language': if there exists at least one machine (a DFA, a PDA, TM, etc) of a given language type, type X, that can be found to accept on a language, and it can be proven that no machine from the type below in the Chomsky hierarchy can accept on that language, then that language is of 'type X', and all the types above it?

If I'm correct in that rather long definition, then, it means that when a textbook says for example that a language is context free, then it means yes there are an infinite number of PDAs or TM's the can be thought of for which the CF language doest not accept, or loops even. But, there exists at least one PDA for which the language accepts on, and there can be no DFA that can accept on the language?

Further, when a textbook says a language is not even recursively enumerable i.e. unsolveable, it means that this language is above recursively enumerable in the Chomsky hierarchy, and that truly it is impossible to solve - that no TM can be designed to accept/reject on it?

If I've missed the point entirely or have been unclear, please do let me know.

A language $mathcal L$ is recursive if there exists a Turing machine $mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $mathcal L$ (i.e. $forall w, mathcal M$ accepts $wiff winmathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.

However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive*

Moreover, classes of languages are often included in each others. By instance, if a language $mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular but you shouldn't make the assumption that it is either. You simply don't know.

As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.

(*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability

a language A that is recursive for some Turing Machine

That's your problem, right there. A language is either recursive or it's not: there's no such thing as "recursive for a specific Turing machine". A language is recursive if there is some Turing machine that decides it.