snippetMinor
What is an example of set $A$, that is decidable if $AA$, but which is not decidable if it is $A$ alone
Viewed 0 times
alonewhatexamplebutdecidablethatwhichnotset
Problem
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.
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.
Solution
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 :-).
$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 :-).
Context
StackExchange Computer Science Q#81952, answer score: 3
Revisions (0)
No revisions yet.