[FOM] RE: Feasibility
V.Sazonov at csc.liv.ac.uk
Tue Dec 28 07:53:52 EST 2004
Quoting Matt Insall <montez at fidnet.com>:
> <<Say, postulate that (i) the "set" F of feasible numbers is
> closed under +1 (and even under +), once there is no clear
> boarderline between feasible and non-feasible, but that
> (ii) 2^1000 is not in F. >>
> Thank you for the reference. I have not yet read all of it, but it seems to
> me that the choice of 2^1000 for a non-feasible number is too specific for
> the purposes you describe.
The point is that this is more or less *minimal* choice of
non-feasible number for which (i) and (ii) are consistent
(in a sense which should be clearly defined). 2^100 may be
Why do you not just have a symbol (a parameter,
> say K) in your language to stand for ``the ditinguished identifiably
> non-feasible number''? In this setting, I think your axioms would be
> (i) If n is feasible, then n+1 is feasible.
> (ii) K is not feasible.
If K is any concrete number (having a short denotation like 2^1000),
then for the case of sufficiently small K this theory will be
The less is such K the more problematic is consistency of the
resulting axioms and the more these axioms correspond to the
"real" idea of feasibility.
If K is just a symbol, then it could denote what is usually called
non-standard number. This is quite usual and not so problematic
as a "concrete" number K.
> But I do not see the benefit in calling such a K, or any other specific
> natural number, ``inifnity''.
If there is "set" F of (feasible) numbers < K which is closed under
successor then this F, and therefore K, may be naturally called
Let me repeat that the idea of considering some F closed under
successor (and probably also under + and *) and still upper
bounded by some concrete K was seemingly developed first by
Rohit Parikh. He elaborated this in the framework of PA (extended
with such F) with the ordinary FOL as the underlying logic. But
in this case K was too big (something like to exponential tower
of the hight about 2^1000). It was rather unclear how to decrease
this (too rough) upper bound K for F to something like 2^1000.
This proves to be possible, but the price is some kind of
restriction of underlying logic FOL with quite unusual consequences.
These consequences and the price are probably most interesting
subjects to discuss (although my current circumstances will hardly
allow me to reply regularly).
This message was sent using IMP, the Internet Messaging Program.
More information about the FOM