3 ms·
In a declarative language, nothing.
by fernmyth 6y ago
In a declarative language, nothing.
- pron 6y agoBut computation has an intrinsic directionality. If you have two expressions a, and b, and you want to unify them in a declarative language as a = b, then having an unknown subterm in one or the other can make the computation have a completely different complexity, making one direction easy and the other intractable. The P vs. NP problem is a famous question exactly about this directionality. Here's a simple example (in a declarative language that allows non-terminating computation; in a total language similar examples can be given, except "impossible" means intractable rather than non-computable, which, for all intents and purposes is the same): X = terminates?(P(1)) If X is known then finding a P is easy; if vice-versa, finding X is possibly impossible.