Non Chronological Simulation

It is quite possible - at least in theory - to write a simulation which calculates the simulates not in chronological order. Simulation here means that in the end possible histories of the simulated world are derived. The program not necessarily must track events in the simulation in the order of their occurrence in the simulation world.

Aye, you can simulate histories almost as easily as futures so long as you have a clear mechanism to select a legal past state from a present condition. E.g. if you were playing chess backwards, you could move almost everything but pawns in the same way you normally can, pawns could only move backwards, and pieces starting in the graveyard could be introduced after moving an enemy piece away (though limits like having only one white bishop and one black bishop would remain). The simulation becomes considerably more complicated if you need to approach a particular past (e.g. if you need to play chess backwards until all the pieces are in their original configuration), but that's the same sort of issue you encounter if you're attempting to run a regular simulation to a particular future.

The problem below presents a different challenge: simulations with causal loops, where causes in the future introduce effects in the past and vice versa. This would be the same as simulating time travel, where you need to deal with kill-your-own-grandfather problems, or even just sending a letter into the past that would affect the future in such a way as the letter wouldn't have ever been sent.

From SimulationRelationshipToParent:

Consider 'time'. Time as we understand it in our universe is literally a partial-ordering of observations (which is why time is relative), and we keep 'accurate' time by focusing on 'regular' observations (daily cycle of sunrise/sunset, moon going round sun, hands going round clock, vibrations of a cesium atom under pressure of a laser beam, etc.) So, what would it take to make time move backwards in a software simulation? We could take a simulation that has moved forward and attempt to 'rewind' it, but that would be our experience, not that of the agent within the simulation (who has, at the end, no experience of time going backwards). Time going backwards would, for the agent, would require the agent be able to observe and react to events and observations that haven't happened yet, resulting in effects that happen prior to their cause. To make this happen in the simulation, we'd need to deliver the effects before cause to the agent... which would leak into our universe as the ability to determine and observe the effects before the cause (i.e. the ability to receive a message before it has been sent). So, again, this is no-go.

It is possible to provide observation of effect before causes in a simulation involving 'time-machines'. This surely involves hard constraint satisfaction but it is not impossible. The idea is to not simulate in the classical sense of event driven or time frame simulation to play out the simulated time but rather to view the space-time of the simulated universe as a large set of constraints. The normal flow of time is then modeled as local cause and effect dependencies but you can also simulate time machines by adding some constraints from 'now' to 'past' times. Yes this implies cycles and will make a solution much more difficult. Note that this easily takes care of time paradoxes easily. --BlackHat
So you aim to do so by sufficiently limiting the simulation world to what is essentially a reversible computation, eh? I considered this possibility too. If it is not reversible, you have branching from now->past and branching from past->now in a nice little exponential loop consuming space and computation - i.e. you wouldn't have a simulation. As such, this still provides a counter-example of 'Law Independence'.
No. A reversible computation would be if I would start from a 'now' in the simulation world and derive from this the past of that point in time by calculating (reverse simulating) what led there. But this reversible thing is really not of importance for this kind of simulation. After all there are - as you said - infinitely many possible branching futures of a 'normal' simulation of which only one is followed (in most simulations; but see whether simulations). So I could call my reverse simulation example as well a simulation as my constraint satisfaction 'simulation'. In the end all of these examples result in one (or few) simulation runs/results that are 'observed'. -- GunnarZarncke
Correct, a normal simulation can lead to a finite but often absurdly high number of futures BUT only leads to one (often selected pseudorandomly). Nonetheless, a constraints-based programming approach where the past depends on the future and vice versa will still compute exponential possible futures and pasts just to figure out what the frell is going on with the present (because 'the' future can affect the past which can select a different 'the' future which redoes the past, etc.) OR must have only one future for every past and vice versa. The former is intractable in practice - enough to shut down any non-trivial simulation - and the latter is 'reversible'. It is the constraint-satisfaction approach that fails without a reversible world.
So we agree that sending a message in the past can be possible in a suitable simulation. The simulation may be mindbogglingly slow, but theoretically possible at least. And I'm not sure that a SufficientlySmart? constraint solver cannot do this fairly efficiently if the number of these back references are small.

The interesting thing is that normal story-telling effectively means mentally performing NonChronologicalSimulation - albeit on a very coarse scale. If you could program a constraint solver for the above example to first 'tell the rough story', the fitting in the details may be much easier than brute force trying all pasts/futures.

Simulations follow rules to get from a present state to a future state... story tellers aren't so limited. "Telling a rough story" might be a way to write the constraints, though, but simulating towards a particular end isn't nearly as trivial an exercise as simulating towards an open end.

Now the question is: could some sentient life come to reality into such a simulation? If so, and if all data within my computer is encrypted, that means that any arbitrary noise is a universe containing sentient life, if only you had the decryption key... In other words, our reality is only one of the infinite interpretations that could be made out of the "universe noise", other could exist as well (including realities where the universe is infinite in time and space). This is the plot of PermutationCity (GregEgan) -- PhilippeDetournay

Formally defining sentience has proven non-trivial - a lot of people aim such definitions at attempting to ensure humans are the only sentient animal. Definitions for it have included a range of questions such as: can it recognize itself in a mirror? is it capable of subjective thought? can it suffer? The only thing universally recognized is that most humans are sentient... because we defined ourselves to be so. For any given formal definition of sentience, there is little fundamental reason that you couldn't create a software entity capable of meeting it. Some people might consider it impossible for an electronic being to really 'suffer', but even our own neurobiology implies that sufferance is simply stimulation of a particular center of the brain that discomforts us and thus we aim to avoid.

Further complicating things, "sentience" may prove to be continuous. The debate may in some ways resemble DefinitionOfLife.