[FOM] AI-completeness

[Timothy Y. Chow]

Hendrik wrote:
> Take some reasonably well-known formal system.  Players take turns 
> adding additional axioms. Before his turn, a player may challenge his 
> opponent's last move.  That player wins if he shows that the opponent's 
> most recently added axiom is redundant, or that the current set of 
> axioms is inconsistent.

John McCarthy <jmc at cs.Stanford.EDU> wrote:
> The candidate is deciding whether a sentence of first order logic is 
> valid.

These examples make me realize that the issue of *timeframe* seems to be 
very important.

Writing great novels and doing first-rate math take place at rather long 
time scales, on the order of years.  Playing go and translating from one 
language into another take place on the order of hours (although there is 
a long training period required, on the order of years, to become an 
expert in these things.)

Intuitively, it seems to me that Hendrik's example and John's example take 
long amounts of time.  It's true that you *could* force people to make 
decisions within a short time of being exposed to the challenge, but then 
I don't think human beings are very good at that.  Humans will shine best 
in these games if they can take years to think and work as a large 
community.

Now, if the only candidates for AI-completeness were the sorts of tasks 
that people excel at only in groups over many years, then that would 
automatically exclude go and games with a similar flavor.  And maybe 
that's true.

But, Joe Shipman's suggestions of translating poetry and reading CAPTCHAs 
seem halfway plausible candidates for AI-completeness, and they take place 
on the same sort of timescale as go.  So, I wonder if there is a way to 
turn such things into more formally specified games.  The reason that I am 
interested in the game format is that it tends to force people to the 
limits of what is possible.  Machine translation and machine reading of 
CAPTCHAs are already active topics of research, but somehow they don't 
seem to me to be as "focused" as research in chess programs or go 
programs, and I think the game format has something to do with that.

Tim