[FOM] AI-completeness

John McCarthy jmc at cs.Stanford.EDU
Mon Apr 30 17:37:36 EDT 2007

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.

More information about the FOM mailing list