[eyesee]

The neat thing about codecs is they're really defining the bitstream and decoding algorithms.

The encoding algorithms are not written in stone, so to speak. If you can optimize motion estimation encoding using Lucas-Kanade, you can just write that into, say, the x264 encoder and so long as the output is complaint you can expect all existing decoders to play back just fine.

Decoding of course may not be so flexible for compatibility reasons, and of course software is much more malleable than hardware.

Are there video codecs which are (accidentally) Turing-complete?