<p>Yes, depending on what kinds of inputs you consider (see below). <span class="math-container">$KC(x) =^* KCDL(L_x)$</span>, where <span class="math-container">$L_x$</span> is the language which consists only of the string <span class="math-container">$x$</span>, and <span class="math-container">$=^*$</span> means equals up to an additive constant.</p>

<p>The reverse is probably not possible (I think I proved this at one point but can't find it right now). The idea is that Kolmogorov complexity can be solved with a Halting Problem oracle, but KCDL (when the input is a TM) is, if I recall correctly, hard for a higher level of the arithmetic hierarchy.</p>

<p>If you want to talk about the complexity of KCDL you also have to be careful to define what the input is. You want the input to be some finite object - languages are generally not. One natural thing for decidable languages is that the input should be a (total) TM. Another possibility is that the input is a TM, along with a proof (in some fixed, formal language) that the TM is total. Other possibilities exist too.</p>

<p>I haven't seen published work about it, but I thought about it a bit in grad school and proved/observed some elementary results. You can do the same for any computable function, not just a language.</p>

CC BY-SA 4.0
2020-04-23T09:34:30.760Z
For the reverse direction, if $L$ is given as a total Turing machine description $x_L$, then $KC(x_L) =^* KCDL(x_L)$ as well? (if $x_L$ is compressible to $y$ just use $z_L$ that uncompress $y$ and simulate it)
Marzio De Biasi
CC BY-SA 4.0
2020-04-23T12:50:20.257Z
There is a definition of kolmogorov complexity of a computable  function (see 2.2.3): https://arxiv.org/abs/cs/0410002
Raphael Augusto
CC BY-SA 4.0
2020-04-23T14:17:14.743Z
@MarzioDeBiasi: The issue is that there could be a smaller TM, $s_L$ that also decides the same language $L$, but is smaller than $KC(x_L)$. So you just get $KCDL(x_L) \leq^* KC(x_L)$.
Joshua Grochow
CC BY-SA 4.0
2020-04-23T18:57:59.930Z
As I define this quesiton poorly I intend to close it.
Raphael Augusto
CC BY-SA 4.0
2020-04-23T19:03:28.063Z
@RaphaelAugusto: The question has received 3 up-votes, an answer, and seems perfectly well-defined to me. I wouldn't close it...
Joshua Grochow
CC BY-SA 4.0
2020-04-23T19:08:53.197Z
@JoshuaGrochow The problem is that I had not defined the type of the argument of the KCDL function. I'm make another question.
Raphael Augusto
CC BY-SA 4.0
2020-04-23T19:11:48.937Z
@RaphaelAugusto: I think given that this question already has upvotes and an answer it makes more sense to just edit this question than to create a new one merely to fix this small issue.
Joshua Grochow
CC BY-SA 4.0
2020-04-23T19:28:31.683Z
ok. I fix this.
Raphael Augusto
CC BY-SA 4.0
2020-04-23T20:06:56.767Z
Is this true? Let $UNCOMPRESS(x)$ the inverse function of $COMPRESS(x)$ and $COMPRESS(x)$ returns the smallest program that generates the string x, then $KC(f) + KCDL(UNCOMPRESS(x)) \leq KCDL(f)$. As $KCDL(UNCOMPRESS(x))$ is a constant, therefore: $KC(f) \leq^{*} KCDL(f)$.
Raphael Augusto
CC BY-SA 4.0
2020-04-23T20:23:28.440Z
@RaphaelAugusto: I'm afraid I don't understand your last comment. To avoid lengthy discussion here (which the site generally tries to avoid), perhaps we could clarify by email and then you could summarize the result here?
Joshua Grochow
CC BY-SA 4.0
2020-04-24T13:56:16.987Z
There is a large study of minimal indices of computable functions. Here's a survey: https://dl.acm.org/doi/10.1145/2902945.2902957
Lance Fortnow
CC BY-SA 4.0
2020-04-25T15:08:51.100Z
@LanceFortnow: Thanks! It's been so long I had forgotten about the minimal indices stuff :(. Minimal indices seems to really use the ordering on the natural numbers; let MIN(f) take as input a TM and output the minimal index computing the same function as f. Is it obvious that MIN and Kolmogorov-complexity of functions are Turing-equivalent? One is about the ordering on N and the other is about string length. Obv. KC reduces to MIN, but I don't see the other direction (the issue is if there are several programs of minimal length computing f).
Joshua Grochow
CC BY-SA 4.0
2020-04-26T15:23:19.633Z
Might depend on the exact encoding of machines, but the definitions are probably not equivalent. Nevertheless, I'd expect many of the results about MIN to carry over to KCDL.
Lance Fortnow
CC BY-SA 4.0
2020-04-23T03:47:29.697Z
2020-04-23T03:58:36.120Z
2020-04-23T03:58:36.120Z
Joshua Grochow
<p>The Kolmogorov Complexity (KC) of a string <span class="math-container">$y$</span> is the size of the smallest program <span class="math-container">$f$</span> and input <span class="math-container">$x$</span> that: <span class="math-container">$y = f(x)$</span>. Let's define a variation of Kolmogorov's complexity<span class="math-container">$^1$</span>. Suppose a decidable language L, the <em>Kolmogorov Complexity of a Decidable Language</em> (KCDL) <span class="math-container">$^2$</span> is the size of the smallest program that decides on L.</p>

<blockquote>
  <p>Is it possible to reduce KC to KCDL? If so, is it possible to do the reverse?</p>
</blockquote>

<p><strong>Notes</strong></p>

<ol>
<li>I don't know if anyone has already defined this concept, so if you have any reference to that definition or even it doesn't make sense, I would be happy if someone commented.</li>
<li>we can generalize this concept to more classes of languages, but I prefer to keep it simple here.</li>
</ol>

<p><strong>Addendum:</strong> <span class="math-container">$f(w)$</span> is a computable function that decides <span class="math-container">$w$</span> is a word in the language <span class="math-container">$L$</span>. And, KCDL is define as:
<span class="math-container">$$\text{KCDL}(f) = \min \{ \text{length}(p) : \forall p \in TM, p \text{ compute } f\}$$</span></p>

<p>And, note that there is a difference between:</p>

<ol>
<li>the compressed version of a program that computes a function; </li>
<li>the smallest program that computes the same function.</li>
</ol>

<p>If you want to think of the compressed version of a program as the program itself, you cannot forget to take into account the size of the smallest program that does the decompression. Because, first you need to unzip the program file to be able to use it.</p>

CC BY-SA 4.0
2024-03-14T14:49:42.610Z
Did you find out any meaningful results since you posed the question? @Raphael Augusto
mti
<fl.formal-languages><it.information-theory><kolmogorov-complexity><definitions>
Kolmogorov Complexity of a Decidable Language
Raphael Augusto
# Kolmogorov Complexity of a Decidable Language

(Asked by: username_0 on 2020-04-23)

The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable language L, the *Kolmogorov Complexity of a Decidable Language* (KCDL) $^2$ is the size of the smallest program that decides on L.

> Is it possible to reduce KC to KCDL? If so, is it possible to do the reverse?

**Notes**

1. I don't know if anyone has already defined this concept, so if you have any reference to that definition or even it doesn't make sense, I would be happy if someone commented.
2. we can generalize this concept to more classes of languages, but I prefer to keep it simple here.

**Addendum:** $f(w)$ is a computable function that decides $w$ is a word in the language $L$. And, KCDL is define as:
$$\text{KCDL}(f) = \min \{ \text{length}(p) : \forall p \in TM, p \text{ compute } f\}$$

And, note that there is a difference between:

1. the compressed version of a program that computes a function;
2. the smallest program that computes the same function.

If you want to think of the compressed version of a program as the program itself, you cannot forget to take into account the size of the smallest program that does the decompression. Because, first you need to unzip the program file to be able to use it.

**Tags:** fl.formal-languages, it.information-theory, kolmogorov-complexity, definitions

> **Comments:**
> **username_1**: Did you find out any meaningful results since you posed the question? @username_0  

---

## 1 answers

### Answer by username_2 on 2020-04-23. Score: 5

Yes, depending on what kinds of inputs you consider (see below). $KC(x) =^\* KCDL(L\_x)$, where $L\_x$ is the language which consists only of the string $x$, and $=^\*$ means equals up to an additive constant.

The reverse is probably not possible (I think I proved this at one point but can't find it right now). The idea is that Kolmogorov complexity can be solved with a Halting Problem oracle, but KCDL (when the input is a TM) is, if I recall correctly, hard for a higher level of the arithmetic hierarchy.

If you want to talk about the complexity of KCDL you also have to be careful to define what the input is. You want the input to be some finite object - languages are generally not. One natural thing for decidable languages is that the input should be a (total) TM. Another possibility is that the input is a TM, along with a proof (in some fixed, formal language) that the TM is total. Other possibilities exist too.

I haven't seen published work about it, but I thought about it a bit in grad school and proved/observed some elementary results. You can do the same for any computable function, not just a language.

> **Comments:**
> **username_3**: For the reverse direction, if $L$ is given as a total Turing machine description $x_L$, then $KC(x_L) =^* KCDL(x_L)$ as well? (if $x_L$ is compressible to $y$ just use $z_L$ that uncompress $y$ and simulate it)  
> **username_0**: There is a definition of kolmogorov complexity of a computable  function (see 2.2.3): https://arxiv.org/abs/cs/0410002  
> **username_2**: @MarzioDeBiasi: The issue is that there could be a smaller TM, $s_L$ that also decides the same language $L$, but is smaller than $KC(x_L)$. So you just get $KCDL(x_L) \leq^* KC(x_L)$.  
> **username_0**: As I define this quesiton poorly I intend to close it.  
> **username_2**: @RaphaelAugusto: The question has received 3 up-votes, an answer, and seems perfectly well-defined to me. I wouldn't close it...  
> **username_0**: @JoshuaGrochow The problem is that I had not defined the type of the argument of the KCDL function. I'm make another question.  
> **username_2**: @RaphaelAugusto: I think given that this question already has upvotes and an answer it makes more sense to just edit this question than to create a new one merely to fix this small issue.  
> **username_0**: ok. I fix this.  
> **username_0**: Is this true? Let $UNCOMPRESS(x)$ the inverse function of $COMPRESS(x)$ and $COMPRESS(x)$ returns the smallest program that generates the string x, then $KC(f) + KCDL(UNCOMPRESS(x)) \leq KCDL(f)$. As $KCDL(UNCOMPRESS(x))$ is a constant, therefore: $KC(f) \leq^{*} KCDL(f)$.  
> **username_2**: @RaphaelAugusto: I'm afraid I don't understand your last comment. To avoid lengthy discussion here (which the site generally tries to avoid), perhaps we could clarify by email and then you could summarize the result here?  
> **username_4**: There is a large study of minimal indices of computable functions. Here's a survey: https://dl.acm.org/doi/10.1145/2902945.2902957  
> **username_2**: @LanceFortnow: Thanks! It's been so long I had forgotten about the minimal indices stuff :(. Minimal indices seems to really use the ordering on the natural numbers; let MIN(f) take as input a TM and output the minimal index computing the same function as f. Is it obvious that MIN and Kolmogorov-complexity of functions are Turing-equivalent? One is about the ordering on N and the other is about string length. Obv. KC reduces to MIN, but I don't see the other direction (the issue is if there are several programs of minimal length computing f).  
> **username_4**: Might depend on the exact encoding of machines, but the definitions are probably not equivalent. Nevertheless, I'd expect many of the results about MIN to carry over to KCDL.  

---

