Showing posts with label Halloween. Show all posts
Showing posts with label Halloween. Show all posts

Thursday, 26 November 2015

The Cap Theorem and Quantum Gravity

Apologies in advance, this post is both extremely technical in multiple fields, and woefully incomplete, and not nearly as humorous as it ought to be. Dragons be here. I'm incredibly sorry.

CAP Theorem for distributed systems


Brewer's CAP Theorem tells us that every distributed computer system must sacrifice at least one of these properties:
  • C: Consistency
  • A: Availability
  • P: Partition Tolerance.
Astonishingly, if we view the universe as a distributed system, then Quantum Field Theory appears to have (analogues of) each of the three properties from the CAP theorem. But at what cost? Paradoxes. So many paradoxes. The double slit experiment, the twin paradox, the EPR “spooky action at a distance” paradox. Many many more. What if QFT adds to the CAP theorem a fourth property we could sacrifice:
  • C: Consistency
  • A: Availability
  • P: Partition Tolerance
  • T: Time Never Flows Backwards (!!!)

One Million Boulders


Lets look at that last one, Time Never Flows Backwards. Suppose, inside a computer, we're trying to simulate one million boulders rolling down a mountain side. At every time step, we need to generate all the potential collisions between those million boulders, and then process them in the order in which the collision occurs. You're familiar with Newton's cradle? Every one of those collisions can change the magnitude, and order, of any subsequent collision. And worse, round-off error when dicing the time steps means that a collision over *here* can affect a collision over *there*.

(All the gory details can be found here.)

Starting to sound a little bit like quantum dynamics right?

So how do we solve it efficiently? By briefly reversing the arrow of time. We find all the collisions between those boulders in a given timestep, then, optimistically, we solve each boulder independently (“in parallel”) based on it's known potential collisions, as if the order of collisions didn't matter. Then we do a “Fix-Up” phase where we wind the time step backwards and correct any of the boulders where (A) the collision order was incorrect, and (B) the energy of the correction is above a certain tolerance. (In practice the tolerance is very small, this tolerance only serves to prevent certain pathological worst-cases)

Starting to sound a *lot* like quantum dynamics...

Spinfoam

So imagine the spinfoam. In my mind, I visualize it something like this:

Spinfoam sketch, incomplete


In Quantum Chromo Dynamics terms, every face you can see is “Colourless” = (Red + Green + Blue == Red + Red + AntiRed + Green + Blue). In this diagram, the past is down. It's the rigid fixed lattice and appears unchangable. The future is a soup of these faces to the top of the diagram, and the “present” is the coalescing region where the mobile soup phase-transitions into a fixed lattice. Naturally, each edge is the Planck length, equivalently Plank time.
You can even see what we'd call a 'particle', maybe an electron or a neutrino, zipping along at close to the speed of light. In the spinfoam, it appears as a disturbance in the otherwise orderly lattice.

  • <technical> In this diagram, the colours satisfy the Pauli exclusion principle. To represent bosons, simply write integer values at every vertex, and require every cycle-over-edges to sum to zero.
  • This 2D diagram with vertices, edges and faces represents {1xspace+1xtime} dimensions. If we axiomatically accept the Holographic Principle, then it might be possible to represent {3xspace+1xtime} dimensions using only vertices, edges, faces and solids.</technical>
Notice too that, at least in the bottom of the diagram (“past”), the laws of physics are symmetric, and invariant under rotations through both time and space. Despite this local invariance, the time dimension can still be identified by it's global properties. The arrow of time, entropy etc, really does exist and has physical meaning.

Mass

What would happen if we tried to simulate this spinfoam in a computer? Well, most obvious to me, is that 'time' in the simulation does not correlate with the amount of computation required to run the simulation. Indeed, the computation required to run the simulation depends primarily on the search activity to coalesce the soup, and it should be easy to find a computation model where that search activity has a cost that matches Einstein's General Theory of Relativity. i.e. the curvature of a region of space is related to the amount of mass in that region, G = m . r-2

Speed

Now lets take that simulation, and instead of running it on one single computer, we instead run it on a distributed computer system. Suddenly, the CAP theorem applies, and our simulation must sacrifice C, or A, or P.... or.... or..... or... T? What if we could sometimes run our simulation backwards just for a moment, the same as we did when "Fixing up" the simulate of those million boulders. When something doesn't fit, just for a little bit, we'd dissolve that fixed lattice of the past and turn it back into the mobile soup of the future, then reform the lattice into a consistent whole.
From inside the simulation, we'd never be able to send information back into the past (That would be a C violation!), and yet we'd still get “spooky action at a distance” and all those other paradoxes.
But at what cost? Well, surprisingly, only a performance hit. Again, it should be easy to find a model of distributed computation overhead where this performance hit is in exact agreement with Einstein's *Special* Theory of Relativity. Specifically, it's the Lorentz Transform, γ = 1 / sqrt(1-v2.c-2)

Intermission

Okay, big deep breath. The plot-twist is coming up soon. Brace yourself.

String Theory (Science Fiction)


Almost everything I've written above isn't new or novel. It's just a rehash of various discarded String-Theory ideas from the 90s, but with different names and labels. From an experimentalist physicists point of view, String Theory is just not that interesting. In terms of knowing more about the universe we live in, String Theory is pretty much at a dead end. Why? Because it's not *testable*. We can't devise an experiment in the lab to determine if any one of the thousands of competing String Theories makes predictions which match our unique reality. If your theory isn't testable, if there's no way to determine if you theory approximates our universe better than the alternatives, then that's not "Science" with a capital 'S', it's more like Science Fiction with a whole lot more math.

Plot Twist


So here's the plot-twist: CAP Theorem + QFT is testable.
Here's how: Take that exact same familiar double slit experiment we all faithfully reproduced when we first found out about Quantum Mechanics.


  • Setup-1: Use one slit, fire the wave/particle, measure the diffraction. (Gaussian)
  • Setup-2: Use two slits, fire the wave/particle, measure the diffraction. (Interference pattern)

Now, if we compare Setup-1 with Setup-2, if CAP + QFT is true, then Setup-2 will suffer a tiny time-dilation associated with resolving the CAP constraints. If CAP+QFT is true, we could toggle between Setup-1 and Setup-2 and measure the tiny difference in time dilation.

How tiny? So tiny no-one has ever noticed it before.

...so tiny, it would be much much smaller than the time-dilation associated with the mass of the photon itself.

......so tiny, but, at least in theory, so measurable.

What happens if we go into the lab and measure the time dilation difference between Setup-1 and Setup-2, and that difference turns out to be non-zero?

Quantum Gravity and Friends.


So yeah, that's a testable theory of quantum gravity. It neatly explains why gravity is so weak compared with the other forces (aka the Hierarchy problem), and dramatically simplifies the particle zoo.

Furthermore, this theorem is fully consistent with the Copenhagen Interpretation, and even builds on it! By contrast, In this formulation, the many-worlds alternative, however appears to have a vanishingly strict interpretation.

Black holes? Yip.. (I'll let you puzzle that one through, it's actually quite cute :) Naked singularities? Nope.

It neatly explains the uncertainty principle. It's truly a quantum theory from the get-go. The randomness is real ("no hidden variables"), it's even required, but it's certainly not arbitrary or capricious.

All those crazy dimensions from String Theory? Oh yeah, the dimensionality is there, but they're no longer spatial in nature, they're more like properties stacked on the spinfoam.

There's even some tantalising hints on the nature of dark matter and dark energy and inflation in the early universe..

Anyways, I've probably said way too much, as always, if you have any questions, queries or opinions, please let me know in the comments section below!



Saturday, 28 March 2015

Pixel Scaling

I'm converting the maps from the amiga version of Super Skidmarks to work on mobile devices for Skidmarks 2015.



Normally when we scale an image, we treat it as a continuous tone image, like a photograph:
Cubic
One option is to just leave the pixels as is. It gives it a retro feel, but doesn't really capture what computer monitors in the 90s used to look like. We used to call this mode "fatbits":

Fatbits

And yet a third way is to use a pixel-art rescaling algorithm, like xBRZ.
xBRZ

Click through on the images to see full res.

Which do you think I should use? Any other techniques I should consider?

Thursday, 19 September 2013

Random

Lately, I've been tuning the "Drop-Rate" of pickups in Scooter Boy.  It's actually a lot like handing out candy at Halloween.

Allow me to use this handy diagram to explain:

Too little Candy
Too much Candy
Not enough candy to go 'round - some people walk away empty handed.Everyone is all full of sugary goodness, and they don't want any more.

But that's not actually what I wanted to talk about today.

I wanted to talk about Pigeons.

The Pigeon Food Dance

There was a famous set of experiments back in the '30s that revolved around withholding candyfood from pigeons.  In one of these experiments, the amount of time between successive drops was random. It turns out that each of the pigeons developed a (unique) ritualistic food dance. In happy pigeon land, it was the completion of the dance which caused the food to appear.

Now the curious thing was, the time it took for the pigeon to complete the dance was slightly longer than the average time between drops.

So when the pigeon completed the dance, there was a better than 50/50 chance of getting food.  And if not, well repeating the dance a second time would surely do it!

(Have you ever timed how long it takes to reboot your computer when you've got Tech Support on the phone?) 

Random Drop Rates

For most of Scooter Boy's development,  I've been using random drop rates.  Power ups would appear, seemingly at random.  Sometimes you'd get lots, and sometimes you'd go ages without seeing any.

Worse still, changing the drop rate, by changing the percentage of a drop, was very clumsy. You'd double or quadruple the drop rate, play the game, and the results would be... well ... random... There was no way to tell if your change was making the game better.

In short, random drops, just aren't fun!

A Drop Rate Schedule

I'm in the process of changing all those drop-rate percentages into times. 30±10 seconds between drops.  Or 120±60.  It's so much more measurable. And it turns out, it's a lot more fun too.  As a player, it feels like the powerups are rewarding your effort.

So down with Mathematical Randomness! Lets make the game match the player's expectations. Lets put the fun first!