# Natural numbers of great kolmogorov complexity

Before I ask my question, let me give you a mini-preamble: in 2006, during an animated discussion on feasibility, ultrafinitism, and what else on FOM, I introduced (informally, and to speak the tuth, quite vaguely) a seemingly new notion: UNUTTERABILITY (see here for ref).

By that I roughly meant the following: take for instance the number

$BIG=100000000000000^{100000000000}^{100000000000}$.

$BIG$ is certainly a huge number, in the obvious sense: if you try to expand it out as $SSSS...0$ you end up with a monumentally huge string. On the other hand, this "number" is rather small as a term, in fact I just wrote it: it denoting term above is small (of course, in case I talk to a martian who does not know the recursive definition of exp I will have to add that to the cost, but that does not make my BIG number much bigger, as far as its denotation is concerned).

So, this means that beyond the usual take on feasibility, there should be (or so it seems to me) another notion, namely utterability :

a number is utterable if there is at least one of its denoting terms which is feasible.

Obviously what I just stated is not a definition:to turn this into serious math, let us say that one operates in some extension $T$ of basic arithmetics $Q$, and that one has fixed a rigid notion of feasibility, say a number is feasible if it is less than $BIG$ above. Finally, one can take a formalized version of Kolmogorov-Chaitin complexity for the last part: a number $n$ in the ambient theory T is $BIG$-utterable iff its kolmogorov complexity as a symbol is less than $BIG$: a computer whose resources are bounded by $BIG$ and which knows the rules of $T$ can at least utter that number, ie print and store one of its denoting terms.

All right, now my question(s):

can I find a $T$ where it is consistent to postulate the existence of unutterable numbers? And if yes, what can be said of their distribution?

PS obvious post-scriptum: BIG is there just as an example, you can either choose your favorite version of a big number (Graham, Friedmann's TREE, or what else), or even let it undefined, and simply add a F(x) predicate for feasible, a' la Parikh.

• What language are the terms in? The standard language of arithmetic has no exponentiation symbol. – Emil Jeřábek supports Monica Jun 11 '11 at 19:10
• Good question. Ok, to start, let us say that we take as T =IDELTA_0 + exp(), so you have your exponentiation, and enough power to prove its totality. We may need somewhat more perhaps, to speak meaningfully of something like (unutterability axiom): there exists a x such that for each y, if y is a code of a term denoting x, its kolmogorov complexity is greater than BIG. – Mirco A. Mannucci Jun 11 '11 at 19:22
• There are only finitely many formulas of a given length l in T, so in particular there are only finitely many natural numbers which are "l-utterable". – Łukasz Grabowski Jun 11 '11 at 19:29
• There is a technical point that Kolmogorov complexity is not a property of a number: it's a property of a number and a universal prefix-free code. Any number could be coded by the string "aa" if you just pick the right code. This also works for effective theories; for any $n$ we could make an effective theory with a new constant symbol $c$ and an axiom that says $c$ denotes $n$, so that $n$ is now utterable in our theory. My point is that this approach will not give you a philosophically absolute sense of "utterable" in the way that one might hope. – Carl Mummert Jun 12 '11 at 3:27
• @Mirco Mannucci: You are using the term "feasible" in a nonstandard way. The usual definition applies to algorithms, not terms, and an algorithm is "feasible" if the computational cost is bounded by a polynomial in the number of input symbols. This doesn't seem to quite fit here. Also, the phrase "postulate the existence of unutterable numbers" is unclear to me. Can you give a particular theory and a particular axiom whose consistency is in question? – Sidney Raffer Jun 12 '11 at 4:03

Any theory containing $I\Delta_0+\mathit{EXP}+B\Sigma_1$ and having a universal evaluator for your terms (which $I\Delta_0+\mathit{SUPEXP}$ does, if you stick to the arithmetical language and exponentiation) proves that there exist numbers with arbitrary large Kolmogorov complexity of terms. In fact, considering terms instead of the numbers themselves can only decrease the Kolmogorov complexity by an additive constant, so it is a rather pointless thing to do.
• I don't know. I just made a quick estimate on what one needs to formalize the usual argument that there are strings arbitrary large Kolmogorov complexity. The argument is basically an application of the pigeonhole principle to the predicate "Turing machine $M$ outputs $w$ and then halts", which is $\Sigma^0_1$-complete, hence I don't know how to do it with anything weaker than $\Sigma^0_1$-induction. The complexity of any functions has nothing to do with this. – Emil Jeřábek supports Monica Jun 11 '11 at 19:51
• Wait, I can do better. First, $I\Delta_0+\mathit{SUPEXP}$ has a Turing machine evaluating exponential terms, hence it formalizes the reduction to ordinary K.c. above. Then, if every string of length $x+1$ is computable by a T.m. of length $\le x$, I can use collection to get a bound on the transcripts of all these T.m. computations, reducing the function violating PHP to $\Delta_0$. Hence $I\Delta_0+\mathit{SUPEXP}+B\Sigma_1$ is enough. This theory is $\Pi^0_2$-conservative over $I\Delta_0+\mathit{SUPEXP}$, hence it's p.t.c.f. are the 4th level of Grzegorczyk hierarchy. – Emil Jeřábek supports Monica Jun 11 '11 at 20:10
I don't understand the question. On the face of it, of course there are unutterable numbers even in Q. Let the set H = $\{1,2,3,...,2^{BIG}\}$. Then H has cardinality $2^{BIG+1}$. At most $2^{BIG}$ of these numbers have denotations that fit in $\le BIG$ bits. So at least half the members of H don't have such denotations and are therefore unutterable. Did you mean something different?