<p>I think a candidate for such a set <span class="math-container">$\mathbb{B}$</span>, or something very much like it, could be produced by considering an infinite sequence of singleton languages: <span class="math-container">$L_1=\{w_1\},L_2=\{w_2\},\ldots$</span> --- where the <span class="math-container">$w_1\cdot w_2\cdot\ldots$</span> 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.</p>

CC BY-SA 4.0
2020-01-02T08:24:43.220Z
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
CC BY-SA 4.0
2020-01-02T09:39:34.563Z
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
CC BY-SA 4.0
2019-12-31T12:06:39.677Z
2019-12-31T12:06:39.677Z
Aryeh
<p><strong>Disclaimer:</strong> I am not a theoretical computer scientist. </p>

<p>The set of decidable problems <span class="math-container">$\mathbb{D}$</span> is countable so <span class="math-container">$\lvert \mathbb{D} \rvert = \lvert \mathbb{N} \rvert$</span> and this led me to the following idea. </p>

<p>Given two decision problems <span class="math-container">$p,q$</span> in <span class="math-container">$\mathbb{D}$</span> and <span class="math-container">$\mathcal{M}_p,\mathcal{M}_q$</span> the minimal-length Turing Machines deciding <span class="math-container">$p$</span> and <span class="math-container">$q$</span> we may say that <span class="math-container">$p$</span> and <span class="math-container">$q$</span> are relatively prime if: </p>

<p><span class="math-container">\begin{equation}
K(\mathcal{M}_p|\mathcal{M}_q) = K(\mathcal{M}_p) \tag{1}
\end{equation}</span></p>

<p>and</p>

<p><span class="math-container">\begin{equation}
K(\mathcal{M}_q|\mathcal{M}_p) = K(\mathcal{M}_q) \tag{2}
\end{equation}</span></p>

<p>where <span class="math-container">$K(\cdot)$</span> denotes Kolmogorov Complexity. </p>

<p>I think we should then be able to define <span class="math-container">$\mathbb{B} \subset \mathbb{D}$</span> such that <span class="math-container">$\lvert \mathbb{B} \rvert = \lvert \mathbb{D} \rvert$</span> and: </p>

<p><span class="math-container">\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}</span></p>

<p>where <span class="math-container">$\mathbb{B}$</span> is analogous to the set of primes in <span class="math-container">$\mathbb{N}$</span>. Has this idea been explored? </p>

CC BY-SA 4.0
2019-12-31T12:08:23.203Z
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
CC BY-SA 4.0
2019-12-31T12:20:36.703Z
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
CC BY-SA 4.0
2020-01-01T10:34:29.867Z
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
CC BY-SA 4.0
2020-01-01T12:00:13.320Z
@AndrejBauer Thanks for pointing this out. I removed the point about a bijection between decidable problems and the natural numbers.
Aidan Rocke
<turing-machines><kolmogorov-complexity>
Prime factorisation of decidable problems
Aidan Rocke
# Prime factorisation of decidable problems

(Asked by: username_0 on 2019-12-31)

**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?

**Tags:** turing-machines, kolmogorov-complexity
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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...  
> **username_2**: 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).  
> **username_0**: @AndrejBauer Thanks for pointing this out. I removed the point about a bijection between decidable problems and the natural numbers.  

---

## 1 answers

### Answer by username_1 on 2019-12-31. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_3**: 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)  
> **username_1**: 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.  

---

