[FOM] AI-completeness

[joeshipman@aol.com]

That appears to be AI-hard, but it is only AI-complete if Church's 
thesis ("human computer version" not "quantum computer version") fails. 
-- JS

-----Original Message-----
From: jmc at cs.stanford.edu

   I think that AI complete is a worthwhile notion even though no-one 
has
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.