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

[Vladimir Sazonov]

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 
classical logics leads almost immediately to a formal contradiction. 
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 
concept of feasibility lead to contradictions too easily. We should be 
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,

Vladimir Sazonov


>
> -- hendrik boom


----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.