[FOM] Feasible and Utterable Numbers

[Mirco Mannucci]

Dear FOM Fellows,

First of all I would like to thank Sazonov,Podnieks and Simpson
for replying to my recent posting on "Kolmogorov Feasibility".

Thanks for sharing your thoughts.

I realize that I provided no background for my suggestion, so I will
try to do it here.

My core premise is: from a ultra-formalist standpoint, numbers are nothing
more (and nothing less) than finite equivalence classes of closed arithmetic
terms under provability/calculability.

These classes may change over time as new primitive recursive function
definitions are introduced and new calculations are carried out.

In this scheme, the natural number series is just a finitistic version of the
term model of arithmetic (formed by numbers, i.e. equivalence classes, and
their partial order. Notice that such natural number series are not in general
totally ordered: some equivalence classes may not be comparable.).

Suppose you look at one of these "numbers". It may contain a term of the
form SSSSS....SS0, or it may not. If it does, we can say that that number
is feasible, meaning that an explicit calculation (aka a reduction to its
canonical "successor" form) has already been carried out, or at least we
know it can be.

On the other hand, it is perfectly conceivable that an equivalence class
containing the term 2^1000^1000 exists in some finite term model. I simply
introduce the recursive definition of exp, and (assuming that a term
provably equivalent to 1000 is already there), write it down. This class
presumably denotes an "unfeasible number", as it will not contain a
successor term (unless you have virtually unlimited memory and the
celebrated patience of Job!).

If one wants to make the feasible numbers subset closed under some operation,
"fuzzy equivalence classes of terms" may be considered, in the spirit
of semi-sets and related approaches (something I shall gloss over here,
as it is not the focus of this posting).

            *---------------------------*

Now, I want to change perspectives: from feasibility to utterability.

To begin with, each class can be seen as the set of alternative ways of
denoting a concrete number.

Assume that some measure of complexity on the terms is available to us.
At the most basic level, it could be the length of the term, where the
length is a map from the set of all closed terms to the subset of the form
SS..0, satisfying the standard properties of length.
Or, it could be something more sophisticated, like some "Kolmogorov-like"
complexity, as I clumsily suggested in my previous posting (again, the
Kolmogorov map would be a map from terms to terms; there are no numbers
here).

If I do have any such a notion in my hands, I can gauge the utterability
of an equivalence class by saying:

a "number" is utterable iff there is at least one of its denoting
alternatives that is small.

The natural question is, of course: what does it mean small in this context?

The answer, it seems to me, is that there are several "theories of utterability",
depending on your choice for smallness. For instance, as it has been suggested by
Simpson, I could state that small=feasible complexity (or length). A number
is utterable iff one of its denoting terms has feasible length (or Kolmogorov
complexity, if you choose the Kolmogorov Tao).

With respect to this choice,every feasible number (in the sense specified
above) is utterable, but there are utterable unfeasible numbers,
like 2^1000^1000.

However, as pointed out by Podnieks in his last reply, there could be two
unfeasible numbers that are both utterable, but lots of numbers in between
are unutterable. For instance, 2^1000^1000 and 2^1000^1000^50000 are both
unfeasible and certainly utterable, but can we name all the fellows that
are in-between? Unlikely.

I could also follow an entirely different road and say that small means
much smaller than the size of its standard "successor" description.

Along this road, there could be numbers that are feasible, but not utterable!
(they would be equivalence classes of terms for which no convenient denotation
has been invented yet, or even classes for which no such expedient notation
can ever be found).

But this letter is already way too long (and thus barely feasible), and
almost unutterable....

Best to all

Mirco A. Mannucci