A post on Shared Object shows how to build logic gates inside the VP8 video codec, using nothing but a key-frame and its intra-frame prediction modes.

The setup is simple. Each block in the frame is either all white (pixel value 255) for True or all black (0) for False. Wires running right and down are made with H_PRED and V_PRED, which copy pixel values from the block to the left or the block above. Inputs are plain blocks set to a constant value, and outputs are just labeled wire blocks.

The gates come from TM_PRED, or True Motion prediction, where each pixel equals left + top – top_left, clamped to 0 through 255. Set the top row to 255 and the left column to 0, feed the input into the top-left pixel, and the block computes 255 – INPUT, a NOT gate. Set top_left to 255 and feed two inputs into the top row and left column, and the block computes A + B – 255, an AND gate. That pair is functionally complete, so NAND and anything else follows.

See more at sharedobject.blog.