I agree - I think this is the route for more substantial (centuries) storage. However, I'd probably wouldn't use xml - some variant of http://ronja.twibright.com/optar/ mentioned elsewhere on this page.

I'd include the definition of a simple machine, and the text of a program written in opcodes for the machine, for decoding.