# 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:

$$$$K(\mathcal{M}_p|\mathcal{M}_q) = K(\mathcal{M}_p) \tag{1}$$$$

and

$$$$K(\mathcal{M}_q|\mathcal{M}_p) = K(\mathcal{M}_q) \tag{2}$$$$

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:

$$$$\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}$$$$

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. – Aryeh Dec 31 '19 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... – Aryeh Dec 31 '19 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). – Andrej Bauer Jan 1 at 10:34
• @AndrejBauer Thanks for pointing this out. I removed the point about a bijection between decidable problems and the natural numbers. – Aidan Rocke Jan 1 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) – Bjørn Kjos-Hanssen Jan 2 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. – Aryeh Jan 2 at 9:39