Does the "Andromeda Paradox" (Rietdijk–Putnam-Penrose) imply a completely deterministic universe? Wikipedia article: http://en.wikipedia.org/wiki/Rietdijk–Putnam_argument
Abstract of 1966 Rietdijk paper:

A proof is given that there does not exist an event, that is not already in the past for some possible distant observer at the (our) moment that the latter is "now" for us. Such event is as "legally" past for that distant observer as is the moment five minutes ago on the sun for us (irrespective of the circumstance that the light of the sun cannot reach us in a period of five minutes). Only an extreme positivism: "that which cannot yet be observed does not yet exist", can possibly withstand the conclusion concerned. Therefore, there is determinism, also in micro-physics.

Question:
I realize that this is a very philosophically-heavy topic, but at the same time, it is physical in the strictest sense (in that it's not a "What if" question, but more of a thought experiment, like the Twin Paradox, that follows the logical implications of relativity to some extreme scenario). 
So, setting aside matters of "free will" and whatnot, which I'm not interested in... 
If I understand this article correctly: the content of these papers implies a 100% deterministic universe — one in which the future of any object is "set in stone"; but, at the same time, this future is completely inaccessible to any observer that is in its past (i.e: impossible to predict even given initial conditions, because of small-scale uncertainty, chaos, etc.). 
Are the proofs in these articles are well-accepted? (Meaning that this "everything has already happened depending on the observer" universe is the only conclusion one can arrive at?). 
I was not aware of the Andromeda Paradox before. I can't imagine it being very useful, but it's interesting enough as a mind-bender that I'd've thought one would hear about it more often. 
 A: If you look at the Stanford Encyclopedia of Philosophy entry that is cited by Wikipedia, http://plato.stanford.edu/entries/spacetime-bebecome/ (search down to "Andromeda"), I think you'll see there that the argument is not especially well-accepted (that's how I interpret what's there, anyway; the SEP is usually a pretty good source, they ask good Philosophers for contributions and it's refereed by the Editorial Board). You can be sure that Philosophers argue most sides when questions of what "now" might be or of what its relevance might be are raised. I note that the original papers are in Philosophy journals.
For Physicists, the question is relevant insofar as one takes a Hamiltonian/phase space perspective or a Minkowski space-time (or other 4-Dimensional geometry) perspective, however the choice is often made lightly, depending largely on the relative convenience of the different mathematics for a particular problem.
A: The paradox is as Catalin Martin describes it, to summarise: if two people pass on the street, they can give two very different answers as to what time is it "now" on Andromeda, in a certain technical sense.
However it should be underlined that these two "nows" that the authors are talking about (the two spacelike hypersurfaces orthogonal to their two respective wordlines) have nothing at all to do with what they see (their past light cones), which would be the same as they pass. Their supposed "now" has no effect on them, nor they on it. 
Thus they can't infer determinism, or anything else really, from this. Rather it does seem that they are trying to hang their thesis on an irrelevant mathematical technicality.
Moreover I don't expect I am saying anything controversial here, I expect these proofs would be well-rejected, if they were well-known.
A: I think the fact that point in question is separated in a spacelike way for the two observers does not address the argument put forward by the paradox, as it explicitly states that the two observers are comparing their accounts in the distant future, after it would be possible for the invading fleet to arrive and affect them. Penrose states it as:
"In fact neither of the people can yet know of the launching of the space fleet. They can know only later, when telescopic observations from earth reveal that the fleet is indeed on its way. Then they can hark back to that chance encounter, and come to the conclusion that at that time, according to one of them, the decision lay in the uncertain future, while to the other, it lay in the certain past. Was there then any uncertainty about that future? Or was the future of both people already "fixed"?"
He appeals to the idea that the invading fleet in Andromeda was real at the time of the discussion between the two observers, as far as the approaching observer was concerned, whereas it was not yet real for the stationary observer. Yet there can be no doubt of the occurrence of the invasion of the fleet in the frame of the stationary observer a few days after the observers met, as a decision not to invade would conflict with the observationallly real launch of the invasion in the approaching observer's frame.
A: Einstein train thought experiment
I understand this by analogy with Einsteins train thought experiment. Let's say I am on a sidewalk facing over the street, where two people pass each other in opposite directions (one of them facing Andromeda), while they just pass each other captain Zorg of Andromeda Galaxy decides to attack the earth and launches the attack (he really really does it).
For the guy walking towards Andromeda the attack is being launched now, while for the guy that walks away from Andromeda by reference to his subjective present the decision has not been yet taken (relative to his present/plane of simultaneity). Why have I added me as an observer? in order to complete the analogy with the train. 
In Einstein's train thought experiment, the train is moving in one direction, and I am looking at the train when two lightnings hit it right the second I face a guy standing inside a wagon at the middle of the train. One  lightning hits the front, the other hits the back. There are three apparently simultaneous events from my point of view (guy facing, lightning hits front,other lightning hits back) Einstein says that actually, even though these seem simultaneous they actually occur consecutively with priority to the direction of the movement (front is hit, I face guy, back is hit). What's the analogy with Andromeda? Well, the guys in the Andromeda Paradox scenario are like the lightnings: guy walking towards Andromeda is the lightning that hits the front, Captain Zorg is the guy in the train, Zorg's decision is the train and the guy that walks away is the lightning that hits the back of the train.
Because he is walking towards Andromeda, the first guy's present will "hit" captain's Zorg's decision first, while the for the other guy, that walks in the opposite direction (Like the train is walking away from the back hitting lightning) , the decision has already been taken in the present of the first guy (his actual "past";the train has already been hit by the first lightning). From my point of view, me standing on the sidewalk when these guys pass each other and Zorg decides to invade, in my present all seemed simultaneous, but each of us have our present literally. If all three of us plus captian Zorg live a billion years, Captain Zorg will attack first guy's present time, than my present time, than the third guy present time just because we stood there like that when he took the decision. The interpretation can be philosophic if you want to clarify terms and if you consider this a paradox, I see it as an argument rather than a paradox, an argument that terms of past and future are relative to the observer's plain of simultaneity. Think about Captain Zorg sending a beam of light towards the earth the moment he takes the decision on the direction of the walkers, that's how time flows.
So, what do we learn from this? Never walk towards Andromeda :).
A: 
A proof is given that there does not exist an event, that is not already in the past for some possible distant observer at the (our) moment that the latter is "now" for us.

This sentence is remarkably unclear, but I think I understand what it means. The theorem is that for any two points $P$ and $Q$, there is a point $R$ such that in some inertial coordinate system, $P$ and $R$ have the same $t$ coordinate, and in some other inertial coordinate system, $Q$ has a smaller $t'$ coordinate than $R$.
If that sounds uninteresting, it's because it is. The same thing is true of points in the Euclidean plane and their $y$ and $y'$ coordinates in two Cartesian coordinate systems. To believe that this was interesting, you would have to believe that the quantities $t$ and $t'$ have some sort of metaphysical significance that in fact they do not. They are no more meaningful than $y$ and $y'$.
In Euclidean geometry (or special relativity), there is one reality: the Euclidean plane (or spacetime). There are many different Cartesian (inertial) coordinate systems that you can put on the plane (spacetime). They are just ways of labeling points with tuples of numbers to make calculations easier. The numbers in the tuples don't matter in the end; only the points that they represent matter.
The lines $y=0$ and $y'=0$ in two Cartesian coordinate systems will generally be different lines. It doesn't matter, because neither line means anything. $y$ and $y'$ are just coordinates. They are completely arbitrary.
In another answer, Eric Hawk quoted Penrose:

They [...] come to the conclusion that at that time, according to one of them, the decision lay in the uncertain future, while to the other, it lay in the certain past.

The boldface is mine and marks Penrose's fundamental error, which is think is also Rietdijk's fundamental error, though he didn't say it in so many words.
"Past" here means $\{(t,x,y,z) : t<t_0\}$ where $(t,x,y,z)$ are coordinates in some inertial frame and $t_0$ is some constant. It is absurd to label this set of events as "certain". There is no physically meaningful sense in which they are certain to someone located at $(t_0,x_0,y_0,z_0)$. The events that could reasonably be described as certain to that person are those located in the past light cone ($t-t_0 \le -\big\lVert(x,y,z)-(x_0,y_0,z_0)\big\rVert$), since those are the only events about which that person can have received any information. Though I defined it in coordinate terms, the past light cone is independent of the coordinates, as any physically meaningful notion must be. The two people in this problem have the same past light cone when they meet up, notwithstanding their different choices of coordinate system.
If you assume that events outside of the past light cone are certain, then you can bootstrap that to all future events being certain (determinism). You may as well just assume all events are certain to begin with. Both assumptions are equally unfounded.
A: The viewpoint of relativity is centered in the Observer that acknowledge events using the received photons. The reception (acknowledge and signal to action) is delayed due to the distance to the original events.
To clear any paradox I will use a different conceivable perspective (and infeasible):
Any observer has instant access to a master clock common to all objects of the universe .
 The observers are special: they have instant vision and they know the distance to any event. Additionally they have an infinite memory to record all events of the universe as soon as they really happen.
All such events will be recorded in his future, labeled NOW+delay, where NOW is the present master clock value. This special universe will act as our universe do, if and only if, the observers only react to the recorded events when his running master clock equals the labeled records and...
With this complicated apparatus I have no doubts about what is past or future, what happened when and where.  The dissociation of the knowledge from the trigger for action is the key to evade away from any paradox about past events.
With this frame we can differentiate the absolute past (all events originated before the NOW in the master clock, i.e. we must ignore the delay), and the local past of the observer as the events that already triggered the action.
The description of this frame is incomplete and is useless to try to make it more complete.
The use of the light as a knowledge messenger and trigger for action is  much simpler.  
