On Sep 29, 2008, at 12:23 AM, John F. Sowa wrote: (01)
> Chris,
>
> My previous response was semi-jocular, but I meant it seriously.
>
> AW>>> One approach to this is of course to choose a subset of formal
>>> logic that is (a) useful for AI, (b) decidable, and (c) has
>>> tractable complexity on current computers.
>
> CM> Thanks for the references, Adrian. As you note, that is indeed
>> the central strategy of logic-based AI for dealing with the
>> challenge of undecidability, point (a) especially being the kicker.
>
> That is one of the *fallacies* that I exposed in Section 5 of my
> paper on "Fads and Fallacies about Logic". See below.
>
> Every professor who teaches a course on computational complexity
> should make his or her students memorize the following point:
>
> The language in which a problem is stated has no effect on
> complexity. Reducing the expressive power of a logic does
> not solve any problems faster; its only effect is to make
> some problems impossible to state. (02)
Well, no. It does both of these. It makes some problems impossible to
state, true. But it also can, and often does, make it possible to
solve the problems that it can state much more quickly, because it
reduces the size of the search space. That's not a fallacy, its a fact
of great practical importance. (03)
Pat (04)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (05)
|