There is a difference between determinism in the sense of given a certain input, you allways get a certain output, and determinism in the sense of given a certain input, and knowledge of the sub universe in which the problem applies, get a certain output.

I.e an agent that can reason can deterministically figure out that the most probable way of getting information to complete the answer would be to go out on google and do searches, but we don't deterministically know what the information that exists at that point and time on google, so the answer could be different.