There is certainly a computational tie-in with reasoning: proof construction is an NP-complete problem. Even if you assume that the entity has 'sufficient knowledge', it's still going to take an exponential amount of time to infer arbitrary conclusions from this knowledge.

However, consider that, while proof-construction is NP-complete, proof-checking is not. Checking a proof is computationally simple, and we should expect ourselves to be able to check proofs we ourselves could never discover.

Thus, 'perfectly rational' or even just 'spectacularly rational' AI shouldn't seem incomprehensible, irrational to humans. Its reasons should be utterly simple to comprehend -- and utterly impossible to discover.

Jack Saalweachter @ comp.ai.group google 2006-5-27