Mentioned in

Use-cases for computations, other than running them?

7Vitor

2habryka

4William_S

4William_S

4romeostevensit

3Donald Hobson

New Answer

New Comment

4 Answers sorted by

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!)

Substituting parts of the computation (replace a slow, correct algorithm for part of the computation with a fast, approximate one)

- Formally verifying properties of the computation
- Informally checking properties of the computation (is this algorithm for making loan decisions fair?)
- Debugging the computation, or more generally "modifying the computation to do what you actually want"

The process used to generate a valid computation could itself be a valuable compression/training process of some sort. Characteristics of the final computation might be useful as feedback. I guess generalizing is just taking your listed use cases and seeing the computation in question as either up or downstream from the thing we really care about.

Consider this function

This is valid code that returns True.

Note that you can tell it returns true without doing operations, and a good compiler could too.

Shouldn't this also be valid code?

There are a whole space of "programs" that cant be computed directly, but can still be reasoned about. Computing directly is a subset of reasoning.

In imperative programming languages, the main purpose of a program is to specify a computation, which we then run. But it seems a rather...

unimaginativeuse of a computation, simply torunit.Having specified a computation, what else might one want to do with it?

Some examples:

I'm also interested in more general meta-use-cases for computations, which generate use-cases that aren't just "run the computation". For instance, some patterns in the examples above: