# [FOM] feasible numbers (WAS: n(3) < Graham's number < n(4) < TREE)

Thu Mar 30 16:36:54 EST 2006

```Quoting hendrik at topoi.pooq.com Thu, 30 Mar 2006:

> I suppose some of the the wider questions here are,
>    What precise concepts are suitable as a precise analogue of the intuitive
>    idea "feasible"?

I understand this that the vague concept (semiset) of feasible strings
in a finite alphabet, or for simplicity in the one letter alphabet {1},
should be formalised (likewise the concept of continuous function or
non-Euclidean geometry or of a universe of set theory, etc. were
rigorously formalised in mathematics). However, I see no way to
formalise the concept of feasibility in the framework of a traditional
theory like ZFC. Feasibility is almost completely new concept for
mathematics (if to exclude numerous highly informal and often just
useless speculations around the heap paradox or the like). Therefore an
axiomatic approach seems inevitable with reconsidering the underlying
logic, if necessary. Intuitively, there is no longest possible feasible
finite unary string (feasible number) and, moreover the length of
feasible strings is bounded by a number like 2^1000. Doing this in
So, the logic should be restricted in some way, and the result of this
is rather surprising...

>
>    Do we neet do have a feasible mindset,

As usually developing some appropriate mathematical intuition (like
geometrical in the case of geometry, etc.) is inevitable. Just a
coherent system of intuitions around the idea of feasibility and its
relation with other known mathematical intuitions.

> a feasible logic,

Yes, a kind of. Say, what about a style of reasoning where x+y is
considered as an allowed operation on feasible numbers, but adding new
functional symbol satisfying the axiom 2*x = x+x makes the theory
contradictory? Looks strange? And so what, if this proves to be
unavoidable if we want to rigorously formalise feasibility concept?
There are even more strange things on this way.

a feasible
>    metalogic to talk meaningfully about feasibility, much as we need a
>    constructive mindset to make sense of constructivism?

may be...

See more on all of this in

http://www.cs.nyu.edu/pipermail/fom/2006-February/009746.html

> Are we having trouble reasoning about feasibility because we are
> starting from an infeasible mindset?

Not only. The problem is that the first attempts to formalise the
flexible enough in changing some logical principles whichever strange
the result of these changes might look. If we really want to formalise
feasibility we should try to "survive" in the framework of a formalism
arising, even if this seems unbearable at the first impression, hoping
that after further efforts it eventually will become looking more
reasonable and promising. (Recall continuous, but nowhere differential
curves in Analysis.) The point of all these comments is that some first
attempts of consistent formalisations of the fesaibility concept do
exist.

Best wishes,