# Prime factorisation of decidable problems

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?

• There is a bit of a "type error" in your question, since Kolmogorov complexity is defined on strings, not on decision problems. However, if one blurs the distinction between $p$ and a minimal-length Turing machine deciding $p$, then it makes sense. Dec 31, 2019 at 12:08
• The nice thing about prime factorization in number theory is that it's unique. As my answer below indicates, the sets you seek are about as far from unique as possible... Dec 31, 2019 at 12:20
• The bijection is not computable, which may be a problem, but in any case seems to be unnecessary. Why do you need it at all? Just use a reasonale encoding of decidable problems (and note that not all strings encode such problems). Jan 1, 2020 at 10:34
• @AndrejBauer Thanks for pointing this out. I removed the point about a bijection between decidable problems and the natural numbers. Jan 1, 2020 at 12:00

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.
• If $w_i$ are chosen randomly then each $w_i$ will be a prefix of infinitely many $w_j$ so one would have to be careful (the usual idea being that random words are incompressible enough) Jan 2, 2020 at 8:24
• Perhaps one can choose the $w_i$ iteratively, starting from a single infinite incompressible sequence -- precisely with the criterion that $w_{i+1}$ is such that the OP's condition holds for all the $w_i$'s constructed so far. It remains to rigorously show that such a choice is always possible for any incompressible sequence, but I believe it's true. Jan 2, 2020 at 9:39