inverse function
in [Lisp]
|
From: Jonathan L Cunningham on 17 Feb 2010 05:47 On Sat, 13 Feb 2010 17:40:13 +0000, Tim Bradshaw <tfb(a)tfeb.org> wrote: >On 2010-02-13 17:27:43 +0000, Taoufik said: > >> Does someone know if there is any work done to generate an inverse of >> any given lisp function (if possible). > >Inverses only exist for functions which are 1-1 (is this an injection? >I think it is). So many functions do not have them. Even for those >that do, computing the inverse based on the definition is probably >intractable in general. I have my own private library for doing this for simple arithmetic expressions; I think I've used it about twice: once for the orginal appication back in 1999, and then I found it useful for something else in 2005. (Both spare-time "hobby programming" -- I doubt many of us still work full time writing lisp code! :-/ ) But it's not production quality code... I tend to write code which says "error - this bit not implemented yet" and only implement the bits I actually need at the time! (It's a good idea, if you think it might be useful later, to design as if you intend to implement the whole thing, and put in lots of checks for special cases, even if they can't occur in the current application. Otherwise they'll bite you later, when you've forgotten.) It was useful for writing transformations between coordinate systems in a graphics application. It was only necessary to write the transformation in one direction. Incidentally, it doesn't produce an inverse *function* -- the scaling or transformation was written as a macro, and the inverse was generated by another macro, so I could pass in the name of the macro I wanted an inverse for, and use macroexpand to look at it. For example: (defmacro scale (n) `(1+ (* (1- ,n) *sfactor*))) then (setf y-prime (scale y)) is forwards, and (setf y (invert scale y-prime)) is backwards. Anyway, all that's a comment on the original question. I'm following up to Tim Bradshaw because, while it's true that there may not be a unique inverse, that might not matter, in the sense that *any* inverse might be suitable. For a very simple case, sqrt is "the" inverse of (expt n 2), except that minus the square root is also an inverse. Yet the sqrt function is still useful. Once or twice I've attempted to write an inverse of (Conway's) life. (The cellular automaton thingy.) It was inspired by a story in which some guy sent secret messages as apparently random starting patterns in life, but which after a few hundred generations evolved into words (spelled out as patterns of dots, or live cells). It would be really cool to come up with some minimal pattern of live cells which, after a hundred or a thousand generations spelled out my name. All you need to do is set up your name on the grid, and then run life backwards for a hundred generations. Of course, some patterns are "garden of Eden" patterns: there is no possible previous generation. But usually there are many. (In particular, you can sprinkle isolated live cells throughout any large empty space when generating the previous generation: they'll all die out.) So the interesting question is to find a minimal starting pattern. And that's a hard problem. Jonathan -- Writers: Many are called, but few are chosen.
From: Norbert_Paul on 17 Feb 2010 08:51 Mark Tarver wrote: > This kind of thing is much more tractable in Prolog where f(x) = y is > represented as a dyadic predicate f(X,Y). In theory one can run this > in either direction using either X or Y as the output variable. It > would be possible to build a Lisp interpreter in Prolog which could be > 'run backwards' as it were. In the case of many-one functions > multiple values could be returned. In SWI-Prolog you can even enter X which answers 42. (And gives a nice error message which informs you that the implementors are still working on the question) Anyway, you cannot overcome mathematical limitations by switching to another language. But I suppose you didn't mean that either. Norbert
From: Tim Bradshaw on 19 Feb 2010 10:39 On 2010-02-13 18:58:08 +0000, Pascal J. Bourguignon said: > Otherwise, there's not a lot of work on this matter. (Google returns > more article for: > "inverse turing machine" > than for: > "inverse function" "lambda calculus" > ) There is a whole complexity here which I hadn't thought about at all. The laws of physics are reversible, so presumably any machine which obeys them also is reversible, if you think of it the right way. Your example of CONSTANTLY is some kind of example of not thinking "the right way" about the problem because any non-invertible function throws information away, and that's not allowed in a reversible system. There is a literature on reversible computation (which is quite closely related to the literature on quantum computing I think), but I haven't read anything on this in a long time. The Wikipedia entry (http://en.wikipedia.org/wiki/Reversible_computing) looks quite good. --tim
From: Pascal J. Bourguignon on 19 Feb 2010 12:26 Tim Bradshaw <tfb(a)tfeb.org> writes: > On 2010-02-13 18:58:08 +0000, Pascal J. Bourguignon said: > >> Otherwise, there's not a lot of work on this matter. (Google returns >> more article for: >> "inverse turing machine" >> than for: >> "inverse function" "lambda calculus" >> ) > > There is a whole complexity here which I hadn't thought about at all. > The laws of physics are reversible, so presumably any machine which > obeys them also is reversible, if you think of it the right way. Your > example of CONSTANTLY is some kind of example of not thinking "the > right way" about the problem because any non-invertible function > throws information away, and that's not allowed in a reversible > system. The law of physics that are inversible are incomplete (ie they don't apply to open systems). The universe constantly throws information away too. Or rather afar. Therefore any system smaller than the universe loses information (even the black holes, that should tell you something!). You would have to consider the whole universe, from beginning to end, to be able to enter eternity and use reversible laws. Otherwise, we could use specific hardware, reversible computers, which are computers that take care not to lose any bit of information. On such a computer, constantly would be defined as: (defun constantly (result) (lambda (&rest arguments) (values result arguments))) and you wouldn't be allowed to lose values, so that you'd have to keep all the arguments to your constant functions. > There is a literature on reversible computation (which is quite > closely related to the literature on quantum computing I think), but I > haven't read anything on this in a long time. The Wikipedia entry > (http://en.wikipedia.org/wiki/Reversible_computing) looks quite good. There's a nice paper about a garbage collector on such a reverse computer. http://www.pipeline.com/~hba-ker1/ReverseGC.html See also: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.1005&rep=rep1&type=pdf and http://www.portal.acm.org/citation.cfm?id=1244404 The works about reversible hardware are often motivated by the energy sparing they allow, and vice versa, it's by avoiding dissipating energy, that is information far away in the universe that you can implement a reversible system. -- __Pascal Bourguignon__
From: Rob Warnock on 21 Feb 2010 06:06
Pascal J. Bourguignon <pjb(a)informatimago.com> wrote: +--------------- | Tim Bradshaw <tfb(a)tfeb.org> writes: | > There is a literature on reversible computation (which is quite | > closely related to the literature on quantum computing I think), but I | > haven't read anything on this in a long time. The Wikipedia entry | > (http://en.wikipedia.org/wiki/Reversible_computing) looks quite good. | | There's a nice paper about a garbage collector on such a reverse | computer. | http://www.pipeline.com/~hba-ker1/ReverseGC.html +--------------- Uh... That gets a 404; I think you meant: http://www.pipeline.com/~hbaker1/ReverseGC.html -Rob ----- Rob Warnock <rpw3(a)rpw3.org> 627 26th Avenue <URL:http://rpw3.org/> San Mateo, CA 94403 (650)572-2607 |