joeshipman at aol.com
Tue May 1 18:52:25 EDT 2007
That appears to be AI-hard, but it is only AI-complete if Church's
thesis ("human computer version" not "quantum computer version") fails.
From: jmc at cs.stanford.edu
I think that AI complete is a worthwhile notion even though no-one
proved anything to be AI complete. However, I have a candidate.
The candidate is deciding whether a sentence of first order logic is
valid. Of course, validity in first order logic is undecideable, so
maybe it doesn't suit Shipman and Chow's notion. Nevertheless, it is
a non-trivial and non-obvious candidate. If one could decide first
order validity and also find witnesses for existential statements, one
could solve any problem that can be formulated in first order logic,
including those that use set theory or those in which propositions and
individual concepts are reified.
AOL now offers free email to everyone. Find out more about what's free
from AOL at AOL.com.
More information about the FOM