What you describe is easiest handled with topology. I like the Flatland approach for studying this, but I'm going to make it even more extreme: I'm going to describe the world as though it was 1 dimensional. That way, I can have an additional dimension for time, and one more dimension for this above/below behavior, and still fit within the 3 dimensions that we can deal with intuitively.
In topology, this system would appear as two flat sheets, one above and one below, with interconnections. On the top, time flows one direction (lets arbitrarily call that "to the right"), and on the bottom it flows in another direction ("to the left"). At each point there are two interconnections, one allowing travel from the bottom to the top, and the other allowing travel from the top to the bottom.
With this structure, there is no issue with a "square" above passing a dead-square below. The only reason there would be any issue with this is if there was a "collision" as an object tried to cross from above to below, or from below to above, intersecting with itself or another.
Using this topological structure, it is easier to show that many time paradoxes are not important because the structure of time allows a living thing and a ghost to cross paths without intersecting.
Computation is tricky, because it is always done in a perfect theoretical space that never exists. Real computers always have faults, but the paradoxical effects of computation and time travel always assume a perfect computation engine exists.
Accordingly, if you were to strive after a paradox, you would have to use your observations to create a more perfect computer. You would have to measure the state of the computer precisely enough to prevent a fault from occurring. Fortunately for you, this time topology lets you get away with a lot. You can see the fault, identify it's cause, then travel back in time as a ghost to prevent that fault from occurring.
Making the paradox interesting is that the fault has already been observed. The only way to stop the fault is to change something which was unobserved into something that "corrects" the fault after it happens. In a way this will "consume" the unknownness of the universe, one loop at a time. Your machine will get larger and larger as it becomes dependent on more and more observed values until something happens.
What happens depends a lot on what your rulesets are for the minds of ghosts. If the minds of your square and ghost-square are unafflicted by the backwards and forwards travel of time, then the only thing that stops this computational paradox is the patience of your square. Is it actually willing to spend an infinite amount of time to compute an undecidable problem (which, incidentally, is not a paradox. Similar decision problems such as The Halting Problem are only paradoxes for turing machines, which by definition run in finite time).
There are a few alternatives which could resolve the issue without this infinity. One is to refuse to allow ghosts to travel back to the above world into a state where said ghost could cause a paradox. Attempting to create the computational paradox above would simply cause the universe to refuse to allow the ghost to return to the living to mess with itself. This would create an interesting "true death" for ghosts, where the universe no longer admits them to the world of the living because there is no point in time where the ghost could return that is incapable of creating a paradox. It also creates an interesting purgatory for a ghost which has created a potential paradox which forbids the universe from allowing it to return more than X seconds in the past. That ghost must cycle repeatedly, trying to avoid the creation of accidental paradoxes which shrink its lifespan. Eventually, it may give up, let time pass it by, and accept a true death.
A more boring but consistent approach could be to take a physicalist approach, and make the mind of the living or dead creature be made of matter, thus subject to the same uncertainty principles as the rest of the world. In these worlds, one could perceive a paradox, but the harder one tries to perceive it, the more one's mind is distrupted - it's far easier on the universe to let a few atoms of one of your neurons misbehave than it is to allow a paradox. This is actually a very traditional solution to the time traveler paradoxes: the universe will simply disallow you from doing anything which creates an inconsistent state. It also creates interesting effects known as Strange Loops, such as the main character from Heinlein's All You Zombies.
Another alternative would be to allow the universe to affect the minds of the ghosts to erase information needed to produce the paradox. In this world, one is in control of one's own mind in the world of the living, but obviously one has limited control over the physical world around it. Measurements a la. Copenhagen are allowed. You are allowed to remember any measurements you please, just like in real life. However, once you travel to the world of the dead, the roles shift. You can go anywhere you please in the dead world, allowing you to find opportunities to shift to the above world and wreak paradoxes. However, there's a catch. As you move in the ghost world, you do not have perfect control over your mind. Travel to a location where you could choose to make the printer print "B" instead of "A," and the laws of the universe may force you to forget which letter you needed to print to cause a paradox.
An interesting side effect of the last one is a twist on the "true death" of a ghost. A ghost may travel back in time far enough that it is forced to lose so much knowledge that it forgets how to transfer itself back to the land of the living. It coasts, oblivious, until something kicks it back into the world of the living against its will. However, if one's knowledge consists of nothing but "universal truths," one could theoretically surf backwards against time forever, never forgetting who one is, free of what could easily be called the "cycle of reincarnation."
