2
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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 $w\iff w\in\mathcal 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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks v. much for your help. As to the first part of your answer; indeed, what I wanted to highlight with my (rather long) explanation is that the definition of a language being of a certain type is that it can be found that there exists at least one machine of that type that accepts on the lang? And it's also of all types higher in the Chomsky table. Secondly, and as a corollary, in order to show that a lang is not of a type, you must prove that no machine of that type can exist that accepts the lang, which as you say, is often harder to do. Are my assumptions correct? Thanks! $\endgroup$
    – TheRealPaulMcCartney
    Commented Jan 8, 2019 at 10:42
  • $\begingroup$ The reason for the winding, probably confusing length of my Q though was just to highlight the thought process that the lack of a clear explanation in text books leads novices like me down, but indeed my final conclusion on what defines a language of being of type X, Y or Z and not of others, are the two statements in my comment above? $\endgroup$
    – TheRealPaulMcCartney
    Commented Jan 8, 2019 at 10:46
  • $\begingroup$ @TheRealPaulMcCartney Your statements are correct. For example, for regular languages, to prove a language is regular, you usually design a regular expression and prove that the language defined by the expression and the target language contain the same words. To disprove a language is regular, there exists the pumping lemma (for example). $\endgroup$
    – kutschkem
    Commented Jan 8, 2019 at 16:10
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, that's really what I was trying to get at (with a longer explanation that lays out the initial incorrect thought processes, thanks to unclear textbooks, of novices like me). Am I correct then in saying that "A language is of type X (Regular, RE, CF etc) if it is shown there exists at least one machine that accepts on the language, despite there being an infinite number of machines of that type that don't accept on it?" Do you see what I mean? Further, is it correct to say "to prove a lang is not of a type X, you must show there can be no machine of type X accepting the lang"? $\endgroup$
    – TheRealPaulMcCartney
    Commented Jan 8, 2019 at 12:08
  • $\begingroup$ @TheRealPaulMcCartney Yes, that's correct. (I admit that I didn't actually read your whole question, since it seemed very likely that the answer was already clear from the first couple of paragraphs.) $\endgroup$
    – David Richerby
    Commented Jan 8, 2019 at 12:51
  • $\begingroup$ Ok that's brilliant, thanks very much! Yeah, the Q was quite long cause I wanted to lay out the way in which the unclear textbooks confuse us, no worries. Thanks very much! $\endgroup$
    – TheRealPaulMcCartney
    Commented Jan 8, 2019 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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