Jeff Hawkins defines intelligence as the ability to predict. I think it's a good definition: it allows us to measure intelligence.
I personally prefer (although it's certainly less measurable) Ben Goertzel's definition - the ability to achieve complex goals in complex environments. It's still wishy-washy enough for people to write off any given achievement of AI though, I guess.
I think Deutsch's argument is that there is also creativity (and creative reasoning) that is omitted from today's approaches to AI.