[FOM] Another constructivist query.
Vladimir Sazonov
V.Sazonov at csc.liv.ac.uk
Mon Apr 3 19:24:17 EDT 2006
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.
More information about the FOM
mailing list