HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

What is an example of set $A$, that is decidable if $AA$, but which is not decidable if it is $A$ alone

Submitted by: @import:stackexchange-cs··
0
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.

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 :-).

Context

StackExchange Computer Science Q#81952, answer score: 3

Revisions (0)

No revisions yet.