And we even have an existence proof that such a thing is possible, given enough design time. Unfortunately, the existence proof says nothing about the odds of doing so very quickly -- in less than, say, a million years, which is very quick by historical standards.
The other answer contains an implicit assumption that's not obviously correct: you suggest that complexity only arises when you enumerate every possible dimension of phase space. But physical simulations have been very successful at reproducing complex behaviour from simple rules, without taking into account every particle's state vector.
Finally, did you really try to equate my statement to the statement that Windows could be written in three days? ...
As for this statement:
physical simulations have been very successful at reproducing complex behaviour from simple rules
Absolutely, but it doesn't follow that every complex behavior can be reproduced from simple rules. To overgeneralize from success in one field is the occupational illness of futurists. It's certainly a key problem for Singularitarians, who tend to get so enthusiastic about Moore's Law that they forget that most of the world has nothing to do with microelectronics.
So the real question then becomes does biology tolerate working on an approximation of the underlying physics and does that simulated biology still have the ability to exhibit intelligence. I think the first is a maybe, the second a yes but I couldn't give you any reasons why other than that it might be that our biology needs 'its' physics to operate and that probably anything Turing complete has the potential to exhibit intelligence, regardless of whether or not we find a way to achieve that.
One answer is "They will, and surprisingly quickly. But they will be a completely different set of complex interactions than are observed in the real world, because of some roundoff error in the binary representation of the Nth digit of some apparently unimportant constant. Unfortunately, because the system is complex, you'll probably spend the rest of your career trying to track down that error, and fail."
Another answer is: They would, if the simulation was comprehensive enough. Unfortunately, phase space is big. You just won't believe how vastly, hugely, mind-bogglingly big it is. Seriously: Your mind reels when confronted with the number of different molecular interactions going on inside the "simplest" single-celled prokaryote, so you abstract it away, almost as a reflex, to stop yourself from going mad. Then you abstract away the first-order abstraction. Then you keep going. Soon you begin to imagine that you can model an entire collection of a trillion organisms, just as a naive programmer imagines that they can rewrite Windows in three days if only they use a powerful enough language. It's a mere matter of programming!