[FOM] Another constructivist query.

[Vladimir Sazonov]

Quoting "S. Spijkerman / F. Waaldijk" <sufra at hetnet.nl> Mon, 03 Apr 2006:

[in reply to Bill Taylor]

> your question is therefore really about feasibility. also interesting, but
> more difficult, i believe. a good system which really describes
> feasibility/infeasibility in a sharp way and still allows for good
> mathematics,

Let us hope.

Just another argument in favour of formalising the feasibility:

 From the ordinary constructivist point of view either whites have a 
(finite) winning strategy in chess, or not. It is just a routine to 
calculate which alternative takes place. But from the common sense view 
this is evidently highly non-constructive way of reasoning 
(non-feasibly constructive!). Of course, if somebody will invent a 
feasibly constructive proof that, say, whites win, this will be easily 
accepted by everybody. This is like an example of some algorithm in the 
times when nobody even asked what is the *general* concept of an 
algorithm or of computable function. But what if no feasibly 
constructive proof of winning whites exists? Strictly speaking it is 
unclear what does it mean at all. Genuine mathematical approach would 
consist in formalising what means feasibly constructive. Then the proof 
that something is not feasibly constructive would become possible, at 
least in principle.

Of course, Chess is here mostly for illustrative purpose. Something 
like *finite* version of P=?NP (following the ideas of descriptive 
complexity theory) would be more interesting from mathematical point of 
view. The concept of feasibility is just a way to relate mathematics 
with computing practice dealing exactly with feasible computations. (Is 
not this also a potential way to resolve the problem P=NP?) The formal 
approach to feasibility could also serve as another kind of complexity 
theory.


Vladimir Sazonov



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