How is an algorithm non-implementable?
in [General Programming]
|
Prev: use of goto in C
Next: Sorting in linear time ...
From: Daniel Lidstrom on 26 Apr 2010 08:16 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
From: Andrew Poelstra on 26 Apr 2010 09:36 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. 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. -- Andrew Poelstra http://www.wpsoftware.net/andrew
From: Pascal J. Bourguignon on 26 Apr 2010 14:45 Andrew Poelstra <apoelstra(a)localhost.localdomain> writes: > 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. > > 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. There's also another condition, which is that an algorithms must have a finite description. For example, if you give the algorithm to increment an integer as: (case i (0 1) (1 2) (2 3) (3 4) ...) with an infinite number of clauses, then you don't have an algorithm. Now, an algorithm may be implementable, but useless because it's time or space complexities would be so big that it would not be possible to execute it on any hardware, possibly even not in this universe. Some people would by extension of language, speak of such an algorithm as 'unimplementable', but this is not because you need more time or space than the universe that you cannot write that program. On the other hand, we could imagine an algorithm, that while finite in its description, would require more memory than available to implement as a program, or even more memory than available in the whole universe. Such an algorithm wouldn't be implementable (on the given hardware with the given space limitations, or in the given universe). For example, here is an algorithm to determine if any integer is prime, in O(1). (case i (0 nil) (1 nil) (2 t) (3 t) (4 nil) ... (2^number-of-states-encodable-in-this-universe nil)) This is a finite algorithm even if it is very big, and even if you need a lot of time to factorize all these number to be able to generate it. But in the end, you will have a finite algorithm, that will be able to tell whether any integer representable in this universe is prime in a single step. The only problem is that this algorithm needs more than this universe to be encoded and implemented. In practice, it is an unimplementable algorithm. Notice that the algorithm that generates this algorithm is also implementable (eg you could use Eratostene sieve), but you couldn't execute it because you'd not have a computer big enough and enough time in this universe to execute it (even if it terminates in a finite time, and needs only a finite space). There's almost no point in speaking of infinity, given that we live in a finite time-space universe. -- __Pascal Bourguignon__
From: David Librik on 26 Apr 2010 19:57 Daniel Lidstrom <dlidstrom(a)gmail.com> writes: >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. Another classic example of an algorithm that has proved extremely difficult, perhaps impossible, to implement fully is the Risch Algorithm for indefinite integration. It's 100 pages long, filled with heuristics, and requires the ability to determine if an algebraic expression is uniformly zero. Wikipedia has a fairly reasonable description of it (and its obstacles): http://en.wikipedia.org/wiki/Risch_algorithm - David Librik librik(a)panix.com
From: BGB / cr88192 on 26 Apr 2010 22:11
"Andrew Poelstra" <apoelstra(a)localhost.localdomain> wrote in message news:slrnhtb5jl.6s8.apoelstra(a)localhost.localdomain... > 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. > > 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. > I am left to wonder here if it matters whether or not an algorithm is deterministic... for example, there are some problems which are not easily solved via deterministic means (such as synchronizing the operations of a large number of autonomous units, avoiding key-space collisions, ...) which become trivial given large integers and a random number generator (of the TRNG variety, not some lame PRNG...). granted, if all of this exists in a confined and closed space, one can replace the TRNG with a PRNG over the whole "world", but this would tend to fail terribly for a non-closed world (but does offer the possible advantage that particular/interesting results are repeatable). |