2
$\begingroup$

I want to figure out how two languages are different. If we have TM M and TM N, how would I figure out if the languages are different? My intuition is that if a M accepts an input a and N does not then that would prove the languages are different, right?

I'm not too sure if I'm thinking of this correctly.

$\endgroup$
2
$\begingroup$

Languages are just sets (of strings). As with any pair of sets, you show that they're different by showing that one set contains an element that's not in the other. Note that, in general, the problem of determining whether two Turing machines decide the same language is undecidable, so there's no algorithm you can use to generate such a string, in general. But, for any two given Turing machines, you can still try to figure it out.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A little more information, if you had a black box which told us if an element was in the language how would we tackle if an element is in both a TM M and a TM N? in terms that element is in language of M and language of N $\endgroup$ – user2582622 Mar 14 '17 at 9:52
  • $\begingroup$ The elements of a language are strings. I don't understand what you mean by asking if a string is "in a Turing machine". You mean if it's accepted by that TM? $\endgroup$ – David Richerby Mar 14 '17 at 12:35
  • $\begingroup$ Yeah, that's what I meant $\endgroup$ – user2582622 Mar 14 '17 at 15:47
  • $\begingroup$ You'd have to use something you know about $M$ and $N$ to try to produce a string that's accepted by one and rejected by the other. If all you had was a black box, you wouldn't be able to do anything other than iterate through all strings asking if each one was in the two languages. $\endgroup$ – David Richerby Mar 14 '17 at 16:41
  • $\begingroup$ See, that's what I thought too but the thing w/the blackbox is that it will tell us if an element is in the language of a TM M but if the machine halts or rejects, it will still say the language is not part of the language. If an input comes back saying its not in the language, we don't know if it halted or looped. Sorry I didn't mention that. I'm just trying to figure out a way to identify to send something to the blackbox that will help me determine if M will loop/reject/accept on an element $\endgroup$ – user2582622 Mar 14 '17 at 22:56

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.