Really fun question. One partial idea: you can give the space of programs a finite group structure by using ideas from https://en.wikipedia.org/wiki/Reversible_computing …. And then take a discrete Fourier transform over a finite group. But what does a linear combination of programs mean, initially? Hmm.https://twitter.com/warrenm/status/997326005411897344 …
-
Presumably a linear combination of programs means a quantum superposition. But not much makes sense after that. Is the group just S_{2^n}?
I'd rather an interpretation in terms of conventional computers, which have the non-trivial benefit of existing. Yes, the group will be some permutation group, though of course you'd like to relate the idea back to what it means about programs.