Any semantic question about the program (semantic = about input/output relation, as opposed to syntactic = about the source code itself). Note that this is uncomputable due to rice’s theorem. “Output” includes whether the computation halts.
Find a semantically equivalent computation that fulfills/maximizes some criterion:
more obviously correct
shorter in length
faster to run (on hardware x or model of computation y)
doesn’t use randomness
doesn’t leak info through side-channels
compliant with design pattern x
any other task done by a source-to-source compiler
Find a computation that is semantically equivalent after applying some mapping to the input and/or output:
runs on encrypted input/output pairs (homomorphic encryption)
computation is reversible (required before running on a quantum computer)
redundantly encoded, add metadata to output, etc. Example: run program on untrusted hardware in such a way that the result is trusted (hardware exposed to outer space, folding@home, etc)
Any question about the set of programs performing the same computation.
this computation must take at least x time
this computation cannot be done by any program of length less than x (kolmogorov complexity)
Treat the program as an anthropological artifact.
deduce the state of mind of the person that wrote the program
deduce the social environment in which the program was written
deduce the technology level required to make running the program practical
Any semantic question about the program (semantic = about input/output relation, as opposed to syntactic = about the source code itself). Note that this is uncomputable due to rice’s theorem. “Output” includes whether the computation halts.
Find a semantically equivalent computation that fulfills/maximizes some criterion:
more obviously correct
shorter in length
faster to run (on hardware x or model of computation y)
doesn’t use randomness
doesn’t leak info through side-channels
compliant with design pattern x
any other task done by a source-to-source compiler
Find a computation that is semantically equivalent after applying some mapping to the input and/or output:
runs on encrypted input/output pairs (homomorphic encryption)
computation is reversible (required before running on a quantum computer)
redundantly encoded, add metadata to output, etc. Example: run program on untrusted hardware in such a way that the result is trusted (hardware exposed to outer space, folding@home, etc)
Any question about the set of programs performing the same computation.
this computation must take at least x time
this computation cannot be done by any program of length less than x (kolmogorov complexity)
Treat the program as an anthropological artifact.
deduce the state of mind of the person that wrote the program
deduce the social environment in which the program was written
deduce the technology level required to make running the program practical
etc.
(Thanks for reminding me why I love CS so much!)
Mod note: Fixed formatting of this comment.