Prime factorisation of decidable problems

Question

Disclaimer: I am not a theoretical computer scientist.

The set of decidable problems $\mathbb{D}$ is countable so $\lvert \mathbb{D} \rvert = \lvert \mathbb{N} \rvert$ and this led me to the following idea.

Given two decision problems $p,q$ in $\mathbb{D}$ and $\mathcal{M}_p,\mathcal{M}_q$ the minimal-length Turing Machines deciding $p$ and $q$ we may say that $p$ and $q$ are relatively prime if:

\begin{equation} K(\mathcal{M}_p|\mathcal{M}_q) = K(\mathcal{M}_p) \tag{1} \end{equation}

and

\begin{equation} K(\mathcal{M}_q|\mathcal{M}_p) = K(\mathcal{M}_q) \tag{2} \end{equation}

where $K(\cdot)$ denotes Kolmogorov Complexity.

I think we should then be able to define $\mathbb{B} \subset \mathbb{D}$ such that $\lvert \mathbb{B} \rvert = \lvert \mathbb{D} \rvert$ and:

\begin{equation} \forall b \in \mathbb{B} \forall d \in \mathbb{D} \setminus \{b\}, K(\mathcal{M}_b|\mathcal{M}_d)=K(\mathcal{M}_b) \tag{3} \end{equation}

where $\mathbb{B}$ is analogous to the set of primes in $\mathbb{N}$. Has this idea been explored?

Answer 1

I think a candidate for such a set $\mathbb{B}$, or something very much like it, could be produced by considering an infinite sequence of singleton languages: $L_1=\{w_1\},L_2=\{w_2\},\ldots$ --- where the $w_1\cdot w_2\cdot\ldots$ form an incompressible sequence. You might be able to shave off a bit here or there (this will strongly depend on the encoding -- which is why Kolmogorov complexity really only makes sense up to an additive constant). But modulo additive constants, this family of strings has the property where being given one of them as input does not in any way help in generating any other one.