tag:blogger.com,1999:blog-11295132.post4999062346864102325..comments2017-03-14T08:49:33.474-07:00Comments on A Neighborhood of Infinity: Types, and two approaches to problem solvingDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-11295132.post-57297365837897192172014-09-06T16:38:00.094-07:002014-09-06T16:38:00.094-07:00@chad I finally got around to looking at that stac...@chad I finally got around to looking at that stackexchange link. As usual, my rule of thumb "90% of statements involving the term "Turing complete" are incorrect" seems to hold. The example given is part of a large family of recurrence relations that are trivial to solve and Mathematica's RSolve will handle it.<br /><br />Your own examples are a bit harder and I don't know how to attack them generally. If I were writing a compiler I'd throw expressions of the form SUM of POLYNOMIAL*EXPONENTIAL at them and solve for the coefficients.Dan Piponihttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-69810130919687676802014-05-17T12:58:50.345-07:002014-05-17T12:58:50.345-07:00The intro reminded me of a recent post on cstheory...The intro reminded me of a recent post on cstheory, http://cstheory.stackexchange.com/questions/22578/would-it-be-possible-for-a-compiler-to-convert-a-recursive-sum-into-the-average<br /><br />The post could be cleaned up, but it asks an interesting question as to if a compiler could recognize and translate between various recursive formulas for the triangular numbers.<br /> <br />$T_{a+b} = T_a + T_b + ab$, addition recursion<br /><br />$T_{ab} = T_aT_b + T_{a-1}T_{b-1}$, quotient recursionChad Brewbakerhttp://www.blogger.com/profile/10443154815748267611noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-60323998046497282632014-05-17T10:04:12.569-07:002014-05-17T10:04:12.569-07:00@quiz If you partition any set into a bunch of sub...@quiz If you partition any set into a bunch of subsets then you have two ways of looking at the situation. You can think of the subsets as being *sub*sets. But you can think of the collection of subsets itself as being a quotient set. So you can move back and forth between the two views.<br /><br />A Galois connection (http://en.wikipedia.org/wiki/Galois_connection) is also something that allows you to go back and forth between quotient and sub- things. (That article also mentions abstract interpretation.)<br /><br />So to some extent it's a point of view. But in different contexts one or other view can seem more natural.Dan Piponihttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-48176641910280422872014-05-17T09:31:34.813-07:002014-05-17T09:31:34.813-07:00I think you could argue that the partition step of...I think you could argue that the partition step of quicksort is a quotienty algorithm: to sort xs, we take the quotient of less-or-greater-than-pivot, and sort in the quotient. Compare to merge sort, which does the division into subproblems as the first step.Quizhttp://www.blogger.com/profile/01935712406320139010noreply@blogger.com