On 3/24/2012 2:35 PM, Simon Spero wrote:
> In the case of Prolog, we're never in P to begin with... (01)
That is certainly true. And that is one is one of its
greatest strengths. (02)
> With prolog, the biggest problem is that, by requiring all
> possible proof trees to be explored, any infinite search trees
> that might not be explored in a successful positive query will
> lead to non-termination in what should be a successful negative
> query. (03)
Yes. That is why you should never let naive users make design decisions
about what languages and algorithms to use to solve their problems. (04)
Some points: (05)
1. Computational complexity is first and foremost a property
of *problems* -- and only indirectly and *misleadingly*
a property of languages. (06)
2. Restricting the expressive power of a language *cannot* improve
its efficiency on any problem. It merely makes some problems
impossible to express. (07)
3. All useful programming languages are Turing complete, but they
can be used very efficiently for a huge number of problems.
They solve polynomial-time problems in polynomial time. (08)
4. As a useful programming language, Prolog is able to express
problems that may take exponential time or be undecidable
for some inputs, but efficiently solvable for other inputs. (09)
5. But Prolog can also be very efficient for polynomial-time
problems. (010)
6. In fact, many people translate restricted languages like OWL
to Prolog in order to make them run faster. (011)
For more information, see the following article: (012)
http://www.jfsowa.com/pubs/fflogic.pdf
Fads and fallacies about logic (013)
John (014)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: 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 join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J (015)
|