MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
1

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

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

closed as too localized by Andreas Blass, Andres Caicedo, Mark Sapir, Henry Cohn, Benjamin Steinberg Apr 30 2012 at 2:33

1 Answer

4

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.

link|flag
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 2012 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 2012 at 14:48

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