Chaitin's famous incompleteness theorem states that for every r.e. theory $T\supseteq Q$ in the language of arithmetic, there is a constant $d_T$ such that for any $m\geq d_T$ and any $x$, $T$ can not prove the sentence $K(x)\geq m$ ($K$ is the kolmogorov complexity function). The constant $d_T$ is constructed in such a way:

Let $M_{i_0}$ to be the Turing machine that enumerates the theorems of $T$ and $| M_{i_0}|$ denote the length of this machine. Now if $T$ prove a sentence $K(x)\geq m$, then we can write an algorithm to search for such a $x$ and print the first one. The length of this algorithm is $| M_{i_0}|+\lceil log(m) \rceil+e$ where $e$ is a constant. For sufficiently large $m$'s we have $| M_{i_0}|+\lceil log(m) \rceil+e<m$ so $K(x)<m$, contradicting consistency of $T$. Hence we can choose $d_T$ as the least integer solution for the inequality $| M_{i_0}|+\lceil log(m) \rceil+e<m$.

The *Chaitin constant* of $T$ is defined as the **least** constant $c_T$ such that $T$ can not prove any sentence of the form $K(x)\geq c_T$ (see, e.g. this paper).

My question is about the relation between the two constant $c_T$ and $d_T$. Obviously $c_T\leq d_T$ but can they be equal or $c_T$ is always strictly smaller than $d_T$ ? (We know that Kolmogorov complexity has different definitions and so we can ask if the answer depend on the choice of definition).

the smallest $\Pi_1$ sentence not provable in T" is not computable from description of T, because if it was so, by adding this sentence to T and iterating this work ω-times, we should have a r.e. and $\Pi_1$-complete theory which contradicts the incompleteness theorem. Godel sentence of T is obviously computable from description of T, so for infinitely many theory T, Godel sentence is not the smallest $\Pi_1$ undecidable sentence. $\endgroup$ – Payam Seraji Mar 26 '16 at 17:39