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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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 :-).

Improve this answer
$\endgroup$
4
  • $\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
    Commented Oct 2, 2017 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
    Commented Oct 2, 2017 at 10:24
  • $\begingroup$ Oh right I get it now $\endgroup$
    – Link L
    Commented Oct 2, 2017 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
    Commented Oct 2, 2017 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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