3 ms·
> imagine that the algorithms you write had to work (perhaps slightly differently, but essentially the same) when hit with bit-flips in the code. How would one
by j-g-faustus 10y ago
> imagine that the algorithms you write had to work (perhaps slightly differently, but essentially the same) when hit with bit-flips in the code. How would one do that?
Gray code [1] does it for integers: Any two consecutive values are one bit-flip apart.
Instructions could perhaps be encoded similarly: Say an n-bit gray code represents an instruction. Each instruction has an n-bit ID, IDs are spread evenly over the space of n-bit values, and each instruction code resolves to the ID with the smallest Hamming distance [2].
Then most bitflips would yield essentially the same program, as long as the number of instructions is small compared to the number of n-bit values.
Our CPUs wouldn't run that directly, but I think it should be possible to construct simple bytecode instruction sets where practically any permutation of bits gives a syntactically valid program, and where bit sequences with a small Hamming distance in most cases resolve to similar programs.
[1] https://en.wikipedia.org/wiki/Gray_code https://en.wikipedia.org/wiki/Gray_code
[2] https://en.wikipedia.org/wiki/Hamming_distance https://en.wikipedia.org/wiki/Hamming_distance