Imagine we had a universe where something could come from nothing. Imagine we worked out how to find what happens at t+1, given t. This still wouldn't be enough to know everything. We'd have to know what's going on at some t less than ours (or greater, if we can just figure out t given t+1).

In other words, even a universe with spontaneity still has to have boundary conditions. Nothing exists at t=0 is the most obvious boundary condition, and it's probably the most likely one, but it's not the only possible one. There's no reason it has to be that one.

Incidentally, there's no reason for the universe to begin at the boundary condition. The laws of how systems evolve give how past and future relate (or more accurately, how the current system and the rate at which the current system changes relate). If you're given what happens at t=0, you can calculate t=-1 just as easily as you can t=1. Intuitively, you'd say that t=0 caused t=1, and not the other way around. To the extent that that this is correct, the laws of system evolution do not preclude spontaneity. They only preclude future and past events not matching.