Welcome to MathOverflow

Question

2

1

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.

edited Jan 25 at 5:46

Kaveh
2,187●5●24

asked Jun 11 2011 at 18:56

Mirco Mannucci
2,029●8●18

	What language are the terms in? The standard language of arithmetic has no exponentiation symbol. – Emil Jeřábek Jun 11 2011 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 Mannucci Jun 11 2011 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 2011 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 2011 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? – SJR Jun 12 2011 at 4:03

show 6 more comments

Emil Jeřábek · Answer 1 · 2011-06-11 20:12:56Z UTC

2

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.

edited Jun 11 2011 at 20:12

answered Jun 11 2011 at 19:35

Emil Jeřábek
10.7k●1●25●42

Yes, I would think so too: thank you!!! But if I remember correctly, ISIGMA_1 has essentially the same power of PRA, in other words you have all the primitive recursive functions as total there. What about below that threshold? – Mirco Mannucci Jun 11 2011 at 19:42

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 Jun 11 2011 at 19:51

1

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 Jun 11 2011 at 20:10

I know, I know, it's "its", not "it's". – Emil Jeřábek Jun 11 2011 at 20:15

none · Answer 2 · 2011-06-11 19:26:17Z UTC

0

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?

answered Jun 11 2011 at 19:26

none
1

yes I meant something different . To give you some idea of what I am after, consider the evolution of denotation systems. First we have only 0, S0, SS0... and so on. That is not very efficient, right? so we invented exp, and now we can say 1345, which means 1* 10^3 + 3 *10^2+.. This game has continued to this day. For instance, using Knuth's uparrow notation, we can denote immense numbers with few lines (and of course the recursive definitions of uparrow). Now, my question says essentially this: is consistent to postulate that this "compression by improving on denotations" is limited? – Mirco Mannucci Jun 11 2011 at 19:37

1

No, that isn't possible. As long as we can invent new notation we can always invent new notation for a particular number. – Carl Mummert Jun 12 2011 at 11:25

Natural numbers of great kolmogorov complexity

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.