MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

give example of 2 languages A and B such that A and B are undecidable but there concatenation A.B is decidable.

share|cite|improve this question

closed as too localized by Andreas Blass, Andrés Caicedo, Mark Sapir, Henry Cohn, Benjamin Steinberg Apr 30 '12 at 2:33

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

This looks like homework to me; I'll vote to close. – Andreas Blass Apr 30 '12 at 0:30
Should I delete my answer? – Joel David Hamkins Apr 30 '12 at 0:58
yes you can delete – shreya Apr 30 '12 at 1:38
up vote 4 down vote accepted

Let $A$ contain all even-length strings, plus an undecidable collection of odd-length strings. Let $B$ contain all odd-length strings, plus the empty string, plus an undecidable collection of even-length strings. So each is undecidable, but the concatenation $AB$ consists of all strings and hence is decidable.

share|cite|improve this answer
in place of undecidable set of odd/even length string if i just take union of odd length string+halting problem+null (same for even), it will work i feel – shreya Apr 30 '12 at 1:24
I tried to delete, but unfortunately, the software does not seem to allow me to delete an accepted answer. (And since it is now off the main page anyway, and closed anyway, perhaps it is best simply to let it rest...) – Joel David Hamkins Apr 30 '12 at 14:48

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