13
$\begingroup$

I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?

$\endgroup$
  • 11
    $\begingroup$ I suspect that you might not have a clear idea of what we mean by "language". Can you say what you believe a "language" is? $\endgroup$ – Eric Lippert May 10 '15 at 16:35
  • $\begingroup$ Why do you need to knw that? In what way do you think it might make a difference? $\endgroup$ – babou May 12 '15 at 20:57
29
$\begingroup$

The language recognized by a Turing machine is, by definition, the set of strings it accepts. When an input is given to the machine, it is either accepted or not. Any particular input to that machine is either always accepted (in the language) or always not accepted (not in the language). So there's no mechanism by which a single Turing machine even could accept more than one langauge.

$\endgroup$
  • 6
    $\begingroup$ "By definition" is exactly what I would have said. $\endgroup$ – Dave Clarke May 10 '15 at 9:45
  • 1
    $\begingroup$ @DaveClarke Of course, it is by definition. But this seems to me a bit short, since it also says that we could make our definition different, so that a TM would accept two languages, or any number. I actually disagree with David Richerby's statement that there is no mechanism by which a TM could accept two languages: it is only because we choose to ignore them, and we could do otherwise. Hence the question is not fully answered, imho, if we do not explain what justifies doing so. $\endgroup$ – babou May 10 '15 at 10:07
  • 2
    $\begingroup$ I think the problem here is the language being used to describe "language" itself. A Turing machine accepts anything in the form of a string regardless of our definition of language. The TM defines language by what it accepts, this is not the same as our (human) understanding of language. This is why this answer is good and is "...fully answered" . $\endgroup$ – David Barker May 10 '15 at 12:16
  • 2
    $\begingroup$ I agree with David, the OP most likely read somewhere that Turing machines admit only one language, and is trying to understand what that means. Given that this probably came from a normal source, we can assume they were using the normal definition of "language" as defined in computational theory, and not any other definition. The definition may be arbitrary, but it is a well understood and agreed upon arbitrary definition. $\endgroup$ – Cort Ammon May 10 '15 at 18:40
  • 3
    $\begingroup$ A Turing machine that accepts two languages is a Turing machine that accepts a language that is the union of two languages. $\endgroup$ – Simon Richter May 11 '15 at 6:39
9
$\begingroup$

Think of it this way: a TM is like a computer with a loaded software. Each software does one thing, right? E.g., think of your computer and assume it has only 1 program loaded in it. Then PC+"photoshop" only does photoshop, while PC+"mine sweeper" only sweeps mines.

So a Turing machine is a very simple creature, that on each run gets a single input and outputs either a yes or a no. On which inputs it says yes, and on which it says no -- this is set by the "program" of the TM as determined by its states and transition function. Once these are fixed, the "program" is fixed, and for any given input there is only one answer: Yes or No (accept/reject). This defines exactly a single language = all the inputs that yield a Yes when given to the TM.

On the other hand, the set of all TMs is equivalent to the set of computer+"software" with all possible programs. Now more languages can be decided - but still, each specific TM decides (or recognizes) only one language.

$\endgroup$
  • $\begingroup$ Minor point: I wouldn't say that a TM outputs "either a yes or a no", since this neglects nontermination. This simplification might cause further problems later on. $\endgroup$ – chi May 22 '17 at 12:28
4
$\begingroup$

Turing Machine work as they do because we choose to define them so. We could have more sophisticated definitions, but the question is whether it would serve a purpose, whether it would allows us to do more things. And, as far as we know, the answer is no.

It is very easy to make models of Turing Machines that recognize two languages. Given languages $L_1$ and $L_2$, we could define a TM with 2 kinds of accepting state: one for $L_1$ and one for $L_2$. A TM would be said to accept $L_i$ if it enters at some point a corresponding accepting state. But it would resume computation to see whether it can also enter the other kind of accepting state. And we could require that it later halts, or possibly not. You could then build the entire theory on such machines. It would works and be a lot more complicated than what we usually do.

To answer David Richerby statement that "there's no mechanism by which a single Turing machine even could accept more than one language", it is only because we choose not to consider such mechanisms. Even if you restrict TM to the very standard model, you could say that the input is recognized to be in language $L_1$ when the TM halts in an accepting state with an odd number of steps, and it is in $L_2$ when the TM accepts with an even number of steps. Thanks to non-determinism, this would not prevent the TM from recognizing both of two intersecting languages.

The point is that all kinds of variants can be used to do the theory. Also very different approaches have been tried to model what is computation, such as lambda-calculus, compinatory logic, recursive functions theory, and more.

It has always been shown that none of them does anything that cannot be done by our simple model where TM recognize only one language. To such an extent that it has been conjectured that it does anything that can be done. That is called the Church-Turing thesis. It is the cornerstone of computability theory, that, as far as we know, determines what languages are recognizable, or not.

So we might as well use a simple model, since a complex one will make our life harder, without any real benefit.

Of course, we sometimes use other models because they allow us to better understand some issues.

$\endgroup$
  • $\begingroup$ I believe the first paragraph is a bit misleading. I'm willing to bet that the OP is not asking about why we're defining things this way, but that they didn't even know it was the case. "We could have more sophisticated definitions, but the question is whether it would serve a purpose" makes it seem like you a need to know the purpose of a concept before you can fathom giving it a name -- in my opinion, that's a bad way to learn. $\endgroup$ – interestinglythere May 12 '15 at 4:51
  • $\begingroup$ The OP says he wants to know why TM recognize only one language to understand something else. I am answering him, they do because we define them that way. I add, which is true, that we could use different definitions, but it would not change the theory. That is a way of telling him that whatever he is after, the choice of definition is immaterial, and recognizability may be defined to cover exactly the same sets. The reason for choosing definition is convenience and fruitfulness, and that is why they evolve with time, as well as the way concepts are named or noted. $\endgroup$ – babou May 16 '15 at 15:40
  • $\begingroup$ Okay, that makes sense. I think I'm mostly objecting to the use of "sophisticated" -- it implies that a less simple definition is desirable. $\endgroup$ – interestinglythere May 16 '15 at 21:13
3
$\begingroup$

I'd like to expand on one point in Richerby's answer:

When an input is given to the machine, it is either accepted or not.

The reason for this is that the Turing machine is deterministic: given the same input and starting state, it will always do the same thing every time you run it (either terminate in the same accept state or in the same reject state, or loop forever).

Additionally, we can easily prove that every Turing machine recognizes exactly one language:

Suppose, by contradiction, that a Turing machine M recognizes two distinct languages L1 and L2. Since L1 and L2 are distinct, there must exist a string S that is in L1 but not in L2 (without loss of generality - it could be the other way around but the proof would proceed in the same way from here with L1 and L2 exchanged). Now run M on S. If it accepts, then a contradiction is reached because then S would be in L2. If it doesn't accept (rejects or loops), then a contradiction is reached because S would not be in L1.

$\endgroup$
2
$\begingroup$

A Turing machine recognizes one language because that's the definition of the word recognize: The language a Turing machine recognizes is the set of all strings/inputs for which the Turing machine accepts.

$\endgroup$
  • 2
    $\begingroup$ Welcome to Computer Science! Your answer is (IMO) correct but I don't think it adds to the pre-existing answers. We have plenty of unanswered questions and it would be much more interesting and productive to answer one of those than to repeat existing answers. $\endgroup$ – David Richerby May 10 '15 at 15:02
  • 1
    $\begingroup$ Thanks! I actually didn't see the currently-accepted answer at first (which I think is good) because it was so short, and I felt like the other answers didn't answer the question in a straightforward way. $\endgroup$ – interestinglythere May 10 '15 at 23:13
1
$\begingroup$

The answer to this depends on what exactly you understand when you mean "Turing machine". There is three components to any computational model (restricting to deciders/acceptors here):

  • syntax,
  • semantics,
  • acceptance criteria.

For Turing machines, syntax would be the tuple of state set, alphabets, transition function, and so on. The semantics would the definition of a computation, that is to describe how to apply the transition function in order to derive the tape content after some steps. The acceptance criterion is to say, "when this happens, we stop and the result is that".

Now, are Turing machines only syntax and semantics to you, or do you include the acceptance criterion as well? If you do the former, any TM can accept multiple languages by using different acceptance criteria; you can even conceive acceptance critera that allow for multiple accepted languages (think about two-parameter TMs, for instance). If you do the latter, however, there is no wiggle room and the usual acceptance criterion does indeed allow for exactly one language per TM (of this type).

The usual definition and usage of the term in TCS includes all three components. That makes sense because, in particular, changing the acceptance criterion can change the class of objects the automaton represents drastically, so we need to fix the criterion in order to know what we talk about.

As an example, compare finite automata and Büchi automata. Syntax and semantics are exactly the same, but one accepts finite words while the other accepts infinite words!
Try to figure out what happens if you plug the acceptance criterion of Büchi automata into the TM definition.

Now, why is the usual acceptance criterion a meaningful one? As long as you restrict yourself to language of finite strings, not much will change by having multiple languages per TM, on the conceptual level: we will still be able to accept the same set of languages. So we stick to the simpler model. That is not to say, however, that a more involved model can not be useful for modelling in applications -- but that's beyond the scope of TCS (which holds definitorial authority).

$\endgroup$
0
$\begingroup$

Suppose we have a TM $M_{1}$ that recognizes $L_{1}$ and $L_{2}$ where $L_{1} \neq L_{2}$. Suppose there is a string $s_{1}$ where $s_{1} \in L_{1}$ and $s_{1} \notin L_{2}$. Then $M_{1}$ accepts $s_{1}$, but $s_{1} \notin L_{2}$ so $M_{1}$ cannot accept $s_{1}$, thus we have reached a contradiction. The other case plays the exact same, eg $s \in L_{2}$ and $s \notin L_{1}$. Therefore, a TM accepts only one language.

To say a TM $M$ recognizes a language $L$ means that for every string $s \in L$, $M$ accepts $s$, and for every string $s$ that $M$ accepts, $s \in L$.

$s \in L \iff M$ accepts $s$

To understand the existence of non-recognisable languages, consider the definition of decidable languages. To say a language is decidable means that the language is recognizable and co-Turing recognizable. If there were no non-recognizable languages, then every language would be decidable. This is false, see $A_{TM}$.

$\endgroup$
  • $\begingroup$ It's not necessary to prove that a TM recognizes just one language: that's immediate from the definition of "recognize". Given that definition, it's not even clear what it means for a TM to accept more than one language (as you suppose in your first sentence) or whether any deduction from such an assumption (as in your third sentence) is valid. Proof by contradiction only works if the deductions are watertight: here, the error could be in the assumption about how a TM that recognizes a TM behaves, rather than in the assumption that such a machine exists. $\endgroup$ – David Richerby May 11 '15 at 15:39
-2
$\begingroup$

A language is a set of strings. Isn't the union of two languages L1, and L2 a set of strings (let's call it L3), and so would be another language? Then, if the Turing machine recognizes both languages, it recognizes L3, a single language.

$\endgroup$
  • 2
    $\begingroup$ But the Turing machine doesn't recognize both languages unless they're actually the same. Recognizing L1 means that it doesn't accept any string outside L1; recognizing L2 means that it doesn't accept anything outside L2. If L1 and L2 are different, it cannot recognize both. $\endgroup$ – David Richerby May 22 '17 at 0:41
-3
$\begingroup$

no other answers point out the existence of the Universal Turing Machine(s) as first described/ discovered by Turing in his halting proof. yes a TM accepts a single recursively enumerable language, but the UTM can recognize any recursively enumerable language if it is encoded on the input along with the input string. so the question has some zenlike quality. TMs both accept only a single language and all possible encodable languages.

$\endgroup$
  • 4
    $\begingroup$ No. A universal Turing machine accepts the single language $\{\langle M,x\rangle\mid M\text{ accepts }x\}$ for some encoding $\langle-\rangle$ of Turing machines and inputs. $\endgroup$ – David Richerby May 11 '15 at 6:51
  • $\begingroup$ & how is that different than whats written? $\endgroup$ – vzn May 11 '15 at 14:59
  • 2
    $\begingroup$ Recognizing codings of languages is not the same thing as recognizing languages. $\endgroup$ – David Richerby May 11 '15 at 15:32
  • $\begingroup$ yes exactly as stated $\endgroup$ – vzn May 11 '15 at 17:28
  • 1
    $\begingroup$ @DavidRicherby I think this is a matter of perspective. One can certainly view a universal TM as accepting many languages; just write it as $\{ (m, x) \mid m = \langle M \rangle, \dots \}$ and look at languages of $x$ for each fixed number $m$ (currying/smn). Restricting TMs to one parameter is universal, but not necessary. $\endgroup$ – Raphael May 12 '15 at 8:46

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.