FOM: unsurveyability

[Vladimir Sazonov]

M. Randall Holmes wrote:

> One may also deny the validity of induction principles; the typical
> ultrafinitist probably does accept that given natural numbers can be
> multiplied, but he may doubt that exponentiation can be applied to
> even rather small and familiar numbers (2^1000 might be doubted to
> exist).

If multiplication operation is postulated as *total* function then
applying multiplication by 2 one thousand of times (which is not
so many) will give 2^1000. Successor and addition operations are
much less "dangerous", however we should be also very careful.
Moreover, we should fix a formalism where, with a firm guarantee,
existence of such infeasible numbers as 2^1000 will not be provable
(by feasible proofs). Note, that Parikh's formalization of
feasibility satisfies only a weaker property.


Charles Silver wrote:

>         I somehow missed this.  Could you please provide a reference to
> the article or book by Parikh in which such systems are featured?  Are any
> of these systems non ad-hoc and "natural"?

I think they are sufficiently natural for describing firstly 
some essential features of feasibility. Of course, there are also 
some shortcomings and very unusual features. The main 
achievement is that these systems are mathematically *rigorous* 
so that instead of (or additionally to) often unclear 
philosophical discussions around feasibility we may investigate 
corresponding formalisms. As Professor R.Gandy once noted me, 
R.Parikh was the first who showed that feasibility indeed can be 
treated as mathematically coherent notion.

Cf. the details in my postings to fom from Nov 5, 1997 and in

Parikh, R. (1971) Existence and feasibility in arithmetic, JSL,
36, (3), 494--508.

Sazonov, V., On feasible numbers, in: Leivant D., ed., Logic and
Computational Complexity, LNCS Vol. 960, Springer, 1995, pp.30--51.
(also available via my home page)


Vladimir Sazonov
-- 			   | Tel. +7-08535-98945 (Inst.),
Computer Logic Lab.,	   | Tel. +7-08535-98953 (Inst.),
Program Systems Institute, | Tel. +7-08535-98365 (home),
Russian Acad. of Sci.	   | Fax. +7-08535-20566
Pereslavl-Zalessky,	   | e-mail: sazonov at logic.botik.ru
152140, RUSSIA		   | http://www.botik.ru/~logic/SAZONOV/