The recent article on overcomingbias suggesting the Fermi paradox might be evidence our universe is indeed a simulation prompted me to wonder how one would go about gathering evidence for or against the hypothesis that we are living in a simulation.  The Fermi paradox isn't very good evidence but there are much more promising places to look for this kind of evidence.  Of course there is no sure fire way to learn that one isn't in a simulation, nothing prevents a simulation from being able to perfectly simulate a non-simulation universe, but there are certainly features of the universe that seem more likely if the universe was simulated and their presence or absence thus gives us evidence about whether we are in a simulation.

In particular, the strategy suggested here is to consider the kind of fingerprints we might leave if we were writing a massive simulation.  Of course the simulating creatures/processes may not labor under the same kind of restrictions we do in writing simulations (their laws of physics might support fundamentally different computational devices and any intelligence behind such a simulation might be totally alien).  However, it's certainly reasonable to think we might be simulated by creatures like us so it's worth checking for the kinds of fingerprints we might leave in a simulation.

Computational Fingerprints

Simulations we write face several limitations on the computational power they can bring to bear on the problem and these limitations give rise to mitigation strategies we might observe in our own universe.  These limitations include the following:

1. Lack of access to non-computable oracles (except perhaps physical randomness).
   
   While theoretically nothing prevents the laws of physics from providing non-computable oracles, e.g., some experiment one could perform that discerns whether a given Turing machine halts (halting problem = 0') all indications suggest our universe does not provide such oracles.  Thus our simulations are limited to modeling computable behavior.  We would have no way to simulate a universe that had non-computable fundamental laws of physics (except perhaps randomness).
   
   It's tempting to conclude that the fact that our universe apparently follows computable laws of physics modulo randomness provides evidence for us being a simulation but this isn't entirely clear.  After all had our laws of physics provided access to non-computable oracles we would presumably not expect simulations to be so limited either.  Still, this is probably weak evidence for simulation as such non-computable behavior might well exist in the simulating universe but be practically infeasable to consult in computer hardware.  Thus our probability for seeing non-computable behavior should be higher conditional on not being a simulation than conditional on being a simulation.
2. Limited ability to access true random sources.
   
   The most compelling evidence we could discover of simulation would be the signature of a psuedo-random number generator in the outcomes of `random' QM events.  Of course, as above, the simulating computers might have easy access to truly random number generators but it's also reasonable they lack practical access to true random numbers at a sufficient rate.
3. Limited computational resources. 
   
   We always want our simulations to run faster and require less resources but we are limited by the power of our hardware.  In response we often resort to less accurate approximations when possible or otherwise engineer our simulation to require less computational resources.  This might appear in a simulated universe in several ways.
   
   • Computationally easy basic laws of physics. For instance the underlying linearity of QM (absent collapse) is evidence we are living in a simulation as such computations have a low computational complexity.  Another interesting piece of evidence would be discovering that an efficient global algorithm could be used that generates/uses collapse to speed computation.
   • Limited detail/minimal feature size.  An efficient simulation would be as course grained as possible while still yielding the desired behavior.  Since we don't know what the desired behavior might be for a universe simulation it's hard to evaluate this criteria but the indications that space is fundamentally quantized (rather than allowing structure at arbitrarily small scales) seems to be evidence for simulation.
   • Substitution of approximate calculations for expensive calculations in certain circumstances.  Weak evidence could be gained here by merely observing that the large scale behavior of the universe admits efficient accurate approximations but the key piece of data to support a simulated universe would be observations revealing that sometimes the universe behaved as if it was following a less accurate approximation rather than behaving as fundamental physics prescribed.  For instance discovering that distant galaxies behave as if they are a classical approximation rather than a quantum system would be extremely strong evidence. 
   • Ability to screen off or delay calculations in regions that aren't of interest.  A simulation would be more efficient if it allowed regions of less interest to go unsimilated or at least to delay that simulation without impacting the regions of greater interest.  While the finite speed of light arguably provides a way to delay simulation of regions of lesser interest QM's preservation of information and space-like quantum correlations may outweigh the finite speed of light on this point tipping it towards non-simulation.
4. Limitations on precision.
   
   Arguably this is just a variant of 3 but it has some different considerations.  As with 3 we would expect a simulation to bottom out and not provide arbitrarily fine grained structure but in simulations precision issues also bring with them questions of stability.  If the law's of physics turn out to be relatively unaffected by tiny computational errors that would push in the direction of simulation but if they are chaotic and quickly spiral out of control in response to these errors it would push against simulation.  Since linear systems are virtually always stable te linearity of QM is yet again evidence for simulation.
5. Limitations on sequential processing power.
   
   We find that finite speed limits on communication and other barriers prevent building arbitrarily fast single core processors.  Thus we would expect a simulation to be more likely to admit highly parallel algorithms.  While the finite speed of light provides some level of parallelizability (don't need to share all info with all processing units immediately) space-like QM correlations push against parallelizability.  However, given the linearity of QM the most efficient parallel algorithms might well be semi-global algorithms like those used for various kinds of matrix manipulation.  It would be most interesting if collapse could be shown to be a requirement/byproduct of such efficient algorithms.
6. Imperfect hardware
   
   Finally there is the hope one might discover something like the Pentium division bug in the behavior of the universe.  Similarly one might hope to discover unexplained correlations in deviations from normal behavior, e.g., correlations that occur at evenly spaced locations relative to some frame of reference, arising from transient errors in certain pieces of hardware.

Software Fingerprints

Another type of fingerprint that might be left are those resulting from the conceptual/organizational difficulties occuring in the software design process.  For instance we might find fingerprints by looking for:

1. Outright errors, particularly hard to spot/identify errors like race conditions or the like.  Such errors might allow spillover information about other parts of the software design that would let us distinguish them from non-simulation physical effects.  For instance, if the error occurs in a pattern that is reminiscent of a loop a simulation might execute but doesn't correspond to any plausible physical law it would be good evidence that it was truly an error.
2. Conceptual simplicity in design.  We might expect (as we apparently see) an easily drawn line between initial conditions and the rules of the simulation rather than physical laws which can't be so easily divided up, e.g., laws that take the form of global constraint satisfaction.  Also relatively short laws rather than a long regress into greater and greater complexity at higher and higher energies would be expected in a simulation (but would be very very weak evidence).
   
3. Evidence of concrete representations.  Even though mathematically relativity favors no reference frame over another often conceptually and computationally it is desierable to compute in a particular reference frame (just as it's often best to do linear algebra on a computer relative to an explicit basis).  One might see evidence for such an effect in differences in the precision of results or rounding artifacts (like those seen in re-sized images).

Design Fingerprints

This category is so difficult I'm not really going to say much about it but I'm including it for completeness.  If our universe is a simulation created by some intentional creature we might expect to see certain features receive more attention than others.  Maybe we would see some really odd jiggering of initial conditions just to make sure some events of interest occurred but without a good idea what is of interest it is hard to see how this could be done.  Another potential way for design fingerprints to show up is in the ease of data collection from the simulation.  One might expect a simulation to make it particularly easy to sift out the interesting information from the rest of the data but again we don't have any idea what interesting might be.

Other Fingerprints

I'm hoping the readers will suggest some interesting new ideas as to what one might look for if one was serious about gathering evidence about whether we are in a simulation or not.

There's a problem that has occurred to me that I haven't seen discussed anywhere: I don't think people actually wants to assign zero probability to all hypotheses which are not Turing computable. Consider the following hypothetical: we come up with a theory of everything that seems to explain all the laws of physics but there's a single open parameter (say the fine structure constant). We compute a large number of digits of this constant, and someone notices that when expressed in base 2, the nth digit seems to be 1 iff the nth Turing machine halts on the blank tape for some fairly natural ordering of all Turing machines. If we confirm this for a large number of digits (not necessarily consecutive digits- obviously some of the 0s won't be confirmable) shouldn't we consider the hypothesis the digits really are given by this simple but non-computable function? But if our priors assign zero probability to all non-computable hypotheses then this hypothesis must always be stuck with zero probability.

If the universe is finite we could approximate this function with a function which was instead "Halts within K" steps where K is some large number, but intutively this seems like a more complicated hypothesis than the original one.

I'm not sure what is a reasonable prior in this sort of context that handles this sort of thing. We don't want an uncountable set of priors. It might make sense to use something like hypotheses which are describable in Peano arithmetic or something like that.

EDIT at Karma -5: Could the next "good citizen" to vote this down leave me a comment as to why it is getting voted down, and if other "good citizens" to pile on after that, either upvote that comment or put another comment giving your different reason?

Original Post:

Questions about the computability of various physical laws recently had me thinking: "well of course every real physical law is computable or else the universe couldn't function."  That is to say that in order of the time-evolution of anything in the universe to proceed "correctly," the physical processes themselves must be able to, and in real-time, keep up with the complexity of their actual evolution.  This seems to me a proof that every real physical process is computable by SOME sort of real computer, in the degenerate case that real computer is simply an actual physical model of the process itself, create that model, observe whichever features of its time-evolution you are trying to compute, and there you have your computer. 

Then if we have a physical law whose use in predicting time evolution is provably uncomputable, either we know that this physical law is NOT the only law that might be formulated to describe what it is purporting to describe, or that our theory of computation is incomplete.  In some sense what I am saying is consistent with the idea that quantum computing can quickly collapse down to plausibly tractable levels the time it takes to compute some things which, as classical computation problems, blow up.  This would be a good indication that quantum is an important theory about the universe, that it not only explains a bunch of things that happen in the universe, but also explains how the universe can have those things happen in real-time without making mistakes. 

What I am wondering is, where does this kind of consideration break with traditional computability theory?  Is traditional computability theory limited to what Turing machines can do, while perhaps it is straightforward to prove that the operation of this Universe requires computation beyond what Turing machines can do?  Is traditional computability theory limited to digital representations whereas the degenerate build-it-and-measure-it computer is what has been known as an analog computer?  Is there somehow a level or measure of artificiality which must be present to call something a computer, which rules out such brute-force approaches as build-it-and-measure-it?

At least one imagining of the singularity is absorbing all the resources of the universe into some maximal intelligence, the (possibly asymptotic) endpoint of intelligences desiging greater intelligences until something makes them stop.  But the universe is already just humming along like clockwork, with quantum and possibly even subtler-than-quantum gears turning in real time.  What does the singularity add to this picture that isn't already there?