So, we have Locke in the island, obsessed with his hatch in 2004, and he then dreams of something that will be happening to him about two months later in his first trip back in time: a Beechcraft falling from the air. It seems to me that he enters some singularity there, where he can commune with his future/past self: he sees the plane falling, sees Boone badly hurt (Locke would easily remember Boone’s death when he saw the plane during BYL) and begins having problems with his legs (his future self was injured by Ethan in one leg). He even has a look at the compass when looking for the Beechcraft!
Somehow, perhaps because in his exploring around he had gotten close to that place where the plane shouldn’t yet be but was (because of the law of “what happened, happened” and there being just one time line, at least until something else is revealed to us in the show) he was attuned to that singularity and got a dream and a lot of rare experiences out of it.
This extremely strange situation would be the proper “Deus ex machina” from the title, I mean, past Locke getting insight from future Locke in a quite unusual (normally impossible) way. (As noted by spartan32, this is something that has happened to Desmond in a few different ways and occasions).
I believe this possibility of an unconscious communing with the future self travelling through the past would be facilitated here and there because of some geographical or psychological situation. I do think this is the main reason why Rose was so sure that Bernard did survive the crash. The future selves of Rose and Bernard had lived together in that island for at least three years by the time they crashed, so that, due perhaps to the stress of the situation, the near-death experience, or just because this couple (in their future) had happened to be together in that same beach before, Rose could have just deeply felt the certainty that she was going to meet her husband again.