Equations over Sets of Natural Numbers with Addition Only

Artur Jez & Alexander Okhotin
Systems of equations of the form $X=YZ$ and $X=C$ are considered, in which the unknowns are sets of natural numbers, ``$+$'' denotes pairwise sum of sets $S+T=\ensuremath{ \{ m+n \: | \: m \in S, \; n \in T \} }$, and $C$ is an ultimately periodic constant. It is shown that such systems are computationally universal, in the sense that for every recursive (r.e., co-r.e.) set $S \subseteq \mathbb{N}$ there exists a system with...