How is an algorithm non-implementable?
in [General Programming]
|
Prev: use of goto in C
Next: Sorting in linear time ...
From: Ralph Boland on 27 Apr 2010 03:49 On Apr 26, 6:16 am, Daniel Lidstrom <dlidst...(a)gmail.com> wrote: > Hi, > > apparently there is an O(N) algorithm available for triangulating a > polygon. It was discovered by Bernard Chazelle in 1990. The paper [1] > is 40 pages! I wanted to see this remarkable algorithm. However, I > read that it is too complex even to implement. Naturally I am > wondering how this can be. Can someone explain? Also, out of > curiosity, are there known algorithms in other domains that are non- > implementable? > > [1]http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf > > -- > Daniel I have read Chazelle's paper and can say that it is implementable if you have the time to do the work. But the algorithm is very complex and not worth the EFFORT to do so. There are lots of algorithms in papers on algorithms that are like this but Chazelle's algorithm is worse than most. Even if you implemented Chazelle's algorithm you would then find that in practice it is slower than a number of much simpler non-linear competitors. Thus you would never use it. By the way, my favourite triangulation alorithm is: B. CHAZELLE, J. INCERPI, Triangulation and shape complexity. ACM Transactions on Graphics, 3 (1984), 135-152. It was implemented (1600 lines of C) and I claim it runs in linear time in practice though of course I have no proof of this. My guess would be that the linear time algorithm would take at least 25000 lines of C and then be shown to be much slower than the shape complexity algorithm among others. Ralph Boland
From: Lie Ryan on 27 Apr 2010 06:43 On 04/26/10 23:36, Andrew Poelstra wrote: > On 2010-04-26, Daniel Lidstrom <dlidstrom(a)gmail.com> wrote: >> Hi, >> >> apparently there is an O(N) algorithm available for triangulating a >> polygon. It was discovered by Bernard Chazelle in 1990. The paper [1] >> is 40 pages! I wanted to see this remarkable algorithm. However, I >> read that it is too complex even to implement. Naturally I am >> wondering how this can be. Can someone explain? Also, out of >> curiosity, are there known algorithms in other domains that are non- >> implementable? >> >> [1] http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf >> > > Knuth gave a point-list to define 'algorithm', and two of them > were that an algorithm both terminates before infinity, and is > unambiguiously defined. > > I'm pretty sure those two points alone mean that you can't > have a "non-implementable algorithm" in a meaningful sense. Words is worth as much as you define it. Knuth defined "algorithm" deliberately so that the sort of problems with "unimplementable algorithm" simply doesn't exists. And with his definition, "have definite step" alone avoids this topic entirely. > But if I were to look for such a thing, I might try the field of > quantum computing, since we do not yet have quantum computers on > which to run their algorithms. That wouldn't make any difference to implementability. Any Turing machine can simulate any other Turing machine. And it's known that classic computer can simulate a quantum computer, so there is no class of algorithms that is unique to quantum computer (or at least we haven't found anything yet).
From: Pascal J. Bourguignon on 27 Apr 2010 11:40 Lie Ryan <lie.1296(a)gmail.com> writes: > On 04/26/10 23:36, Andrew Poelstra wrote: >> On 2010-04-26, Daniel Lidstrom <dlidstrom(a)gmail.com> wrote: >>> Hi, >>> >>> apparently there is an O(N) algorithm available for triangulating a >>> polygon. It was discovered by Bernard Chazelle in 1990. The paper [1] >>> is 40 pages! I wanted to see this remarkable algorithm. However, I >>> read that it is too complex even to implement. Naturally I am >>> wondering how this can be. Can someone explain? Also, out of >>> curiosity, are there known algorithms in other domains that are non- >>> implementable? >>> >>> [1] http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf >>> >> >> Knuth gave a point-list to define 'algorithm', and two of them >> were that an algorithm both terminates before infinity, and is >> unambiguiously defined. >> >> I'm pretty sure those two points alone mean that you can't >> have a "non-implementable algorithm" in a meaningful sense. > > Words is worth as much as you define it. Knuth defined "algorithm" > deliberately so that the sort of problems with "unimplementable > algorithm" simply doesn't exists. And with his definition, "have > definite step" alone avoids this topic entirely. > >> But if I were to look for such a thing, I might try the field of >> quantum computing, since we do not yet have quantum computers on >> which to run their algorithms. > > That wouldn't make any difference to implementability. Any Turing > machine can simulate any other Turing machine. And it's known that > classic computer can simulate a quantum computer, so there is no class > of algorithms that is unique to quantum computer (or at least we haven't > found anything yet). But an algorithm implemented on a normal computer might take more than the life of the universe to complete, while the same algorithm implemented on a quantun computer may give its results before. In the former case, the algorithm would be useless, not so in the later. -- __Pascal Bourguignon__ http://www.informatimago.com
From: Daniel Pitts on 27 Apr 2010 16:33 On 4/27/2010 8:40 AM, Pascal J. Bourguignon wrote: > Lie Ryan<lie.1296(a)gmail.com> writes: > >> On 04/26/10 23:36, Andrew Poelstra wrote: >>> On 2010-04-26, Daniel Lidstrom<dlidstrom(a)gmail.com> wrote: >>>> Hi, >>>> >>>> apparently there is an O(N) algorithm available for triangulating a >>>> polygon. It was discovered by Bernard Chazelle in 1990. The paper [1] >>>> is 40 pages! I wanted to see this remarkable algorithm. However, I >>>> read that it is too complex even to implement. Naturally I am >>>> wondering how this can be. Can someone explain? Also, out of >>>> curiosity, are there known algorithms in other domains that are non- >>>> implementable? >>>> >>>> [1] http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf >>>> >>> >>> Knuth gave a point-list to define 'algorithm', and two of them >>> were that an algorithm both terminates before infinity, and is >>> unambiguiously defined. >>> >>> I'm pretty sure those two points alone mean that you can't >>> have a "non-implementable algorithm" in a meaningful sense. >> >> Words is worth as much as you define it. Knuth defined "algorithm" >> deliberately so that the sort of problems with "unimplementable >> algorithm" simply doesn't exists. And with his definition, "have >> definite step" alone avoids this topic entirely. >> >>> But if I were to look for such a thing, I might try the field of >>> quantum computing, since we do not yet have quantum computers on >>> which to run their algorithms. >> >> That wouldn't make any difference to implementability. Any Turing >> machine can simulate any other Turing machine. And it's known that >> classic computer can simulate a quantum computer, so there is no class >> of algorithms that is unique to quantum computer (or at least we haven't >> found anything yet). > > But an algorithm implemented on a normal computer might take more than > the life of the universe to complete, while the same algorithm > implemented on a quantun computer may give its results before. > > In the former case, the algorithm would be useless, not so in the later. Straw-man. We weren't discussing usefulness of algorithms, were we? -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Pascal J. Bourguignon on 28 Apr 2010 01:47
Daniel Pitts <newsgroup.spamfilter(a)virtualinfinity.net> writes: > On 4/27/2010 8:40 AM, Pascal J. Bourguignon wrote: >> Lie Ryan<lie.1296(a)gmail.com> writes: >> >>> On 04/26/10 23:36, Andrew Poelstra wrote: >>>> On 2010-04-26, Daniel Lidstrom<dlidstrom(a)gmail.com> wrote: >>>>> Hi, >>>>> >>>>> apparently there is an O(N) algorithm available for triangulating a >>>>> polygon. It was discovered by Bernard Chazelle in 1990. The paper [1] >>>>> is 40 pages! I wanted to see this remarkable algorithm. However, I >>>>> read that it is too complex even to implement. Naturally I am >>>>> wondering how this can be. Can someone explain? Also, out of >>>>> curiosity, are there known algorithms in other domains that are non- >>>>> implementable? >>>>> >>>>> [1] http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf >>>>> >>>> >>>> Knuth gave a point-list to define 'algorithm', and two of them >>>> were that an algorithm both terminates before infinity, and is >>>> unambiguiously defined. >>>> >>>> I'm pretty sure those two points alone mean that you can't >>>> have a "non-implementable algorithm" in a meaningful sense. >>> >>> Words is worth as much as you define it. Knuth defined "algorithm" >>> deliberately so that the sort of problems with "unimplementable >>> algorithm" simply doesn't exists. And with his definition, "have >>> definite step" alone avoids this topic entirely. >>> >>>> But if I were to look for such a thing, I might try the field of >>>> quantum computing, since we do not yet have quantum computers on >>>> which to run their algorithms. >>> >>> That wouldn't make any difference to implementability. Any Turing >>> machine can simulate any other Turing machine. And it's known that >>> classic computer can simulate a quantum computer, so there is no class >>> of algorithms that is unique to quantum computer (or at least we haven't >>> found anything yet). >> >> But an algorithm implemented on a normal computer might take more than >> the life of the universe to complete, while the same algorithm >> implemented on a quantun computer may give its results before. >> >> In the former case, the algorithm would be useless, not so in the later. > > Straw-man. We weren't discussing usefulness of algorithms, were we? I don't know. I established earlier that there was two meanings of "unimplementable", one being of uselessness. And since by definition an algorithm is a finite object, it is subject to automatic implementability (there is no difference between an algorithm and an algorithmic program, because of Turing equivalence). Therefore I don't see what point there would be to discuss this other unimplementability than that of uselessness. (We're discussing algorithms right? Not semi-algorithms, or thingies that call up on non-algorithms). -- __Pascal Bourguignon__ |