In regards to the Matrix idea, I gave this a bit of thought a while back and I reckon that it might actually be possible to test this idea! The idea behind the test would be the principle that, regardless of how fantastically fast and brilliant a computer is, it would be fundamentally incapable of coping with doing the continuous calculations required to model continuous space and continuous time. This would show up as a signature of a sort of "blocky" space-time that would leave various signatures that could in principle be searched for.
The idea of testing this isn't original, and related ideas have been around before. I found this in the Telegraph:
http://www.telegraph.co.uk/science/science-news/10451983/Do-we-live-in-the-Matrix-Scientists-believe-they-may-have-answered-the-question.html
The headline is a lie, I think. Scientists haven't answered the question, they've suggested how it could be answered. Still, this is typical of media portrayal of Science. The criticism at the end of the article may have a point, too, but I think it's reasonable to say that even the most powerful computer would have to discretise spacetime at some level, otherwise it would take a billion billion years to calculate the first 0.0000000000000000000000000000000000000001 of a second (both numbers made-up, but the point is still correct. If you have to calculate what happens at every number possible you'll never be able to manage it, be the very nature of uncountably infinite numbers).
Anyway, if space is discretised in a way that echoes what is called "Lattice Quantum Field Theory", it could be suggestive that we're living in a computer simulation after all. It would certainly be nice if the idea could be tested, anyway, although on the face of it the answer is almost certainly "No". Whatever computer it is would have to be phenomenally powerful, capable of simulating the behaviour of something like 10^90 atoms (and goodness only knows how many smaller particles still) over a volume of at least 10^80 cubic metres, for something like 10^17 seconds. That would be no mean achievement to pull that computing task off, especially as you need finer graining than atoms (need to operate at the level at least of quarks), and finer spacing than metres (scales of something like 10^-25 metres required) and shorter times than seconds.
All I'm saying is, I would want to do more than just tip my hat to whoever wrote the computer capable of simulating an entire Universe.