Timeline for Is there a "mathematical" definition of "simplify"?
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2013 at 17:35 | comment | added | Joel David Hamkins | I should have said "coarser" rather than "stronger". One way to think about the difference is: you say two expressions are equivalent if they are equal in the actual universe, whereas under the provable-equivalence concept, they are equivalent if they are equal in all possible universes. | |
| Apr 5, 2013 at 17:08 | vote | accept | Craig Feinstein | ||
| Apr 5, 2013 at 9:39 | comment | added | Joel David Hamkins | +1. Henry, that is quite a remarkable result. Your notion of equivalence is stronger than the one I had proposed, since you say two expressions are equivalent if it is true that they define the same function, whereas I had said they are equivalent if it is provable in some fixed theory that they define the same function. For my equivalence, the equivalence classes are c.e., and the algorithmic solution is obtainable as I had described. For your solution, it is quite remarkable that the equivalence classes are not c.e... | |
| Apr 5, 2013 at 2:23 | history | edited | Henry Cohn | CC BY-SA 3.0 |
fixing wrong description of second function $f$
|
| Apr 5, 2013 at 2:09 | history | edited | Henry Cohn | CC BY-SA 3.0 |
Oops, adding a "computable"
|
| Apr 5, 2013 at 1:10 | comment | added | Henry Cohn | So when you say "the set of equivalent forms of an expression is a c.e. non-decidable set" you are missing a complement. And you can easily be justified in saying two expressions are inequivalent, not using the simplifier at all but rather by exhibiting a point at which the functions differ. | |
| Apr 5, 2013 at 1:09 | comment | added | Henry Cohn | By contrast, there is no obvious way to computably enumerate the equivalent expressions (there are various manipulations that guarantee equivalence, but they do not suffice to get all possible equivalences), and in fact it cannot be done. Richardson's theorem proves this, since if you could do it the whole problem would be decidable. | |
| Apr 5, 2013 at 1:08 | comment | added | Henry Cohn | Joel, you are swapping c.e. and co-c.e. In this context (closed-form expressions for real-valued functions, as in Richardson), the set of equivalent forms is co-c.e. and provably not c.e. More explicitly: the set of INequivalent expressions is computably enumerable. These are all computable, continuous functions; if you want to verify that $f \ne g$, you identify a rational point $x$ for which $f(x) \ne g(x)$ and demonstrate this by computing them accurately enough to confine them to non-overlapping intervals. This fits with experience: identities between functions are easily disproved. | |
| Apr 5, 2013 at 0:09 | comment | added | Jacques Carette | Also note that Moses (dl.acm.org/citation.cfm?id=806298 - paywall, google for it for a free version) has an excellent discussion for why 'canonical form' is an exceedingly bad definition of "simplest". | |
| Apr 5, 2013 at 0:06 | comment | added | Jacques Carette | The definition implicit in Joel's comments above is essentially the definition that I have used in my paper (see Carlo Beenakker's answer). The optimal simplified form is indeed uncomputable, as far as I am concerned. I further argue that this 'optimal' is not even particularly desirable, as a difference of just a few bits in representation length should not be considered relevant [since one can always change universal Turing machines anyways and change all codes by a bounded number of bits]. | |
| Apr 4, 2013 at 23:40 | comment | added | Joel David Hamkins | ...just because the current most-simplified forms are not equivalent, since for all you know, a further simplification might make the equivalent. Basically, the set of equivalent forms of an expression is a c.e. non-decidable set. | |
| Apr 4, 2013 at 23:40 | comment | added | Joel David Hamkins | Henry, I stand by my remark. The reason that your argument works with Richardson's theorem is because you require the algorithm to output the optimal simplified form and then halt, so that one knows it is the optimal simplified form. Thus, expressions with different optimal simplified forms and known to be inequivalent, giving the "no" answer for the equivalence problem. But in my description, you never quite know that you have the optimal form, even when in fact you have it, so that you can't ever be justified in saying that two expressions are inequivalent, ... | |
| Apr 4, 2013 at 23:23 | comment | added | user21349 | Your definition of algorithmic is extremely strict. If you relax it just a tiny bit, you can get a different result. For example, suppose I build analytic functions out of expressions involving simpler analytic functions, starting with some simple set of primitives such as addition, exponentiation, and so on. If two such functions are unequal, then they're only going to agree on a set of measure zero. Therefore I can very efficiently determine by numerical sampling (with finite but arbitrary precision) whether two given expressions are equal. It's very difficult to fool such an algorithm. | |
| Apr 4, 2013 at 21:33 | comment | added | Henry Cohn | Weaker versions are possible, for example if you don't require intermediate expressions to be correct. Say, a simplifier that at each time step returns the simplest expression it hasn't yet proven to be inequivalent. That would eventually converge to a correct canonical form, but at the cost of potentially giving incorrect simplifications along the way. | |
| Apr 4, 2013 at 21:31 | comment | added | Henry Cohn | Specifically, interleave simplification computations for all expressions, and output each pair for which partial simplifications agree. If equivalent pairs are guaranteed to eventually reach the same output (a fully simplified canonical form), then this will computably enumerate all equivalent pairs. | |
| Apr 4, 2013 at 21:30 | comment | added | Henry Cohn | I don't think the stronger assertion can be true, although maybe I'm missing something. In Richardson's theorem, the functions are all continuous and computable, in the sense of being able to compute arbitrarily close approximations. This means the pairs of inequivalent expressions are computably enumerable, since one just has to look for rational points at which there's a gap between the two functions. It follows that the equivalent pairs cannot be computably enumerable, or else the equivalence problem would be decidable. However, if I understand right your simplifer would enumerate them. | |
| Apr 4, 2013 at 20:43 | comment | added | Joel David Hamkins | I was saying something stronger. My proposal is that one will eventually and computably arrive at the most simplified form, fully simplified as you put it, but without necessarily realizing that no further simplifications are possible. Thus, one continues to search for further simplifications, even though none are possible. That is, you are assuming that the output of the simplification process is a computable process in the sense that it is completed and a final answer is given, whereas I'm proposing a computable process which gets to the simplified form, without stating that it is finished. | |
| Apr 4, 2013 at 20:16 | history | edited | Henry Cohn | CC BY-SA 3.0 |
added 247 characters in body
|
| Apr 4, 2013 at 20:12 | comment | added | Henry Cohn | @Joel David Hamkins: Hmm, I think there are two meanings of simplify: to make simpler, or to make as simple as possible. The latter meaning is typically used in education (if a teacher asks a student to simplify $x+x+x$, then $2x+x$ will not be an acceptable answer) and often but not always used elsewhere. The argument I gave rules out an algorithm for full simplification, at least with a canonical output, and it shows that there is no algorithm to detect whether futher simplification is possible. However, you are right that it allows the possibility of a scale of simplicity. | |
| Apr 4, 2013 at 17:56 | comment | added | Joel David Hamkins | This process is as in our practice, at the blackboard, where we simplify an expression, but then realize suddenly that further simplifications are possible. | |
| Apr 4, 2013 at 17:56 | comment | added | Joel David Hamkins | The "simplified" form of an expressible is simply the equivalent expression of shortest length and lexically least of that shortest length (or use the least Gödel code, etc.). Thus, the simplification process I am proposing is algorithmic in that we may computably arrive at the simplified version, and furthermore equivalent expressions always arrive at the same expression, so it satisfies your criteria. But the process skirts the contradiction in your objection, since the question of whether our process has completed or not is not computably decidable. | |
| Apr 4, 2013 at 17:55 | comment | added | Joel David Hamkins | I don't think this answer is quite right. Specifically, there seems to be a concept of "simplified" that satisfies your two criteria while stopping short of solving the equivalence problem. Specifically, let us imagine that there is a computable procedure to enumerate all the various equivalent expressions to a given expression, by applying various algebraic rules or deductions of proofs or whatever, so that the set of these equivalence expressions forms a c.e. set. | |
| Apr 4, 2013 at 14:19 | history | answered | Henry Cohn | CC BY-SA 3.0 |