4
$\begingroup$

I encountered a question to give an example of a set $A$ that is not decidable as $A$, but which becomes decidable if it is concatenated with itself, i.e. $AA$.

In case a set $A$ is decidable, then it is easy to see that $AA$ is also decidable, since a $TM$ that decides $A$ can be modified to also recognize $AA$... But I am having a hard time to look for examples given its converse.

$\endgroup$
3
$\begingroup$

You can pick your favourite undecidable language $L$ and build $A$ in this way:

$A = \{ 1 \} \cup \{ 2n \} \cup \{ 2n + 1 \mid n \in L \}$

$A$ contains $1$ and all even numbers, but it also contains ... (I let you try to complete the proof)

Note that I assume that $AA = \{ xy \mid x, y \in A\}$; because if you define $AA=\{ xx\mid x \in A\}$ then it doesn't exist an undecidable language $A$ such that $AA$ is decidable (again I let you try to prove it :-).

$\endgroup$
  • $\begingroup$ Thanks, but in case $x={1}$ and $y=2n+1|n \in L$, wouldn't $xy$ be undecidable because of $y$ being an odd number 'inside' the undecidable part of $A$? $\endgroup$ – Link L Oct 2 '17 at 8:52
  • 1
    $\begingroup$ @LinkL: no because in $AA$ you find: the number 2: $x=1 \in A; y=1 \in A$; all odd numbers greater than 1: $x=1 \in A; y=2n \in A$ and all even numbers greater than 2: $x=2\cdot 1 \in A, y = 2n \in A$ ... so $AA = \{ n > 1 \}$ which is clearly decidable. $\endgroup$ – Vor Oct 2 '17 at 10:24
  • $\begingroup$ Oh right I get it now $\endgroup$ – Link L Oct 2 '17 at 10:25
  • 1
    $\begingroup$ Accidentally the same construction was used answering "Proving that non-regular languages are closed under concatenation", although the question was much more restrictive. $\endgroup$ – Hendrik Jan Oct 2 '17 at 10:28

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.