* Generation of permutations @ 2002-04-29 11:54 Reinert Korsnes 2002-04-30 13:52 ` Ted Dennison 2002-04-30 17:12 ` Wes Groleau 0 siblings, 2 replies; 88+ messages in thread From: Reinert Korsnes @ 2002-04-29 11:54 UTC (permalink / raw) Hi, Are there any good (Ada95) packages for generation of permutations (of elements in array) ? reinert ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-29 11:54 Generation of permutations Reinert Korsnes @ 2002-04-30 13:52 ` Ted Dennison 2002-04-30 14:20 ` Marin David Condic ` (2 more replies) 2002-04-30 17:12 ` Wes Groleau 1 sibling, 3 replies; 88+ messages in thread From: Ted Dennison @ 2002-04-30 13:52 UTC (permalink / raw) Reinert Korsnes <reinert.korsnes@chello.no> wrote in message news:<aajce7$7jb$1@snipp.uninett.no>... > Are there any good (Ada95) packages for generation of permutations > (of elements in array) ? Sadly, that doesn't come up much...outside of homework assignments. ;-) Are you writing a bogosort? -- T.E.D. Home - mailto:dennison@telepath.com (Yahoo: Ted_Dennison) Homepage - http://www.telepath.com/dennison/Ted/TED.html ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 13:52 ` Ted Dennison @ 2002-04-30 14:20 ` Marin David Condic 2002-05-02 12:32 ` Robert Dewar 2002-05-02 15:47 ` Ted Dennison 2002-04-30 15:06 ` Hyman Rosen 2002-05-02 16:24 ` Mark Biggar 2 siblings, 2 replies; 88+ messages in thread From: Marin David Condic @ 2002-04-30 14:20 UTC (permalink / raw) "Ted Dennison" <dennison@telepath.com> wrote in message news:4519e058.0204300552.15317df9@posting.google.com... > Reinert Korsnes <reinert.korsnes@chello.no> wrote in message news:<aajce7$7jb$1@snipp.uninett.no>... > > Are there any good (Ada95) packages for generation of permutations > > (of elements in array) ? > > Sadly, that doesn't come up much...outside of homework assignments. ;-) > > Are you writing a bogosort? > > I once did it for an article in "Ada Letters" called "Junk Facts And The Slowsort". (My resume says that was Ada Letters, Vol 10, Num 1, if that's any help.) It was a *really* slow sorting algorithm. Unfortunately that was so long ago I don't have the code around anymore. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 14:20 ` Marin David Condic @ 2002-05-02 12:32 ` Robert Dewar 2002-05-02 15:47 ` Ted Dennison 1 sibling, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-02 12:32 UTC (permalink / raw) "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:<aam989$99c$1@nh.pace.co.uk>... > I once did it for an article in "Ada Letters" called "Junk Facts And The > Slowsort". (My resume says that was Ada Letters, Vol 10, Num 1, if that's > any help.) It was a *really* slow sorting algorithm. Unfortunately that was > so long ago I don't have the code around anymore. The sorting algorithm that looks like pick x in permutations (s) | sorted (s) is of course fundamentally well known. See Jack Schwartz "On Programming" (Courant Institute, early 1970's) for a discussion of how this algorithm can be automatically transformed into more efficient algorithms. For a more formal discussion of such transformations, see Susan Merrit's Phd Thesis (Courant Institute, sometime in the early 90's, NYU, I was the advisor). Also see Robert Paige's work on formal differentiation systems for an actual implementation of this and similar transformations. In a certain sense, the above "program" is not just an implementation of sorting, it is a fundamental definition of what sorting means. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 14:20 ` Marin David Condic 2002-05-02 12:32 ` Robert Dewar @ 2002-05-02 15:47 ` Ted Dennison 2002-05-02 16:16 ` Mark Biggar 1 sibling, 1 reply; 88+ messages in thread From: Ted Dennison @ 2002-05-02 15:47 UTC (permalink / raw) "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:<aam989$99c$1@nh.pace.co.uk>... > "Ted Dennison" <dennison@telepath.com> wrote in message > > Are you writing a bogosort? > I once did it for an article in "Ada Letters" called "Junk Facts And The > Slowsort". (My resume says that was Ada Letters, Vol 10, Num 1, if that's I did it in Pascal for a undergraduate project back in '87. I needed to compare the actual running times of 3 algorithms with 3 different time behaviors. nlogn and n**2 were easy, but I was wracking my brain for a week to think up a way to sort slower than n**2. At the time I called it "PermuteSort", but others since have named it "bogosort" (http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=bogosort ), and I like that name much better. :-) -- T.E.D. Home - mailto:dennison@telepath.com (Yahoo: Ted_Dennison) Homepage - http://www.telepath.com/dennison/Ted/TED.html ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-02 15:47 ` Ted Dennison @ 2002-05-02 16:16 ` Mark Biggar 2002-05-03 13:04 ` Marin David Condic 2002-05-03 13:13 ` Ted Dennison 0 siblings, 2 replies; 88+ messages in thread From: Mark Biggar @ 2002-05-02 16:16 UTC (permalink / raw) Ted Dennison wrote: > > "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:<aam989$99c$1@nh.pace.co.uk>... > > "Ted Dennison" <dennison@telepath.com> wrote in message > > > Are you writing a bogosort? > > I once did it for an article in "Ada Letters" called "Junk Facts And The > > Slowsort". (My resume says that was Ada Letters, Vol 10, Num 1, if that's > > I did it in Pascal for a undergraduate project back in '87. I needed > to compare the actual running times of 3 algorithms with 3 different > time behaviors. nlogn and n**2 were easy, but I was wracking my brain > for a week to think up a way to sort slower than n**2. > > At the time I called it "PermuteSort", but others since have named it > "bogosort" (http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=bogosort > ), and I like that name much better. :-) There are worse sorts then Bogosort. For example there is 52-pickup sort: repeatedly randomize the list until you notice that it is sorted. -- Mark Biggar mark.a.biggar@attbi.com ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-02 16:16 ` Mark Biggar @ 2002-05-03 13:04 ` Marin David Condic 2002-05-05 0:52 ` Robert Dewar 2002-05-03 13:13 ` Ted Dennison 1 sibling, 1 reply; 88+ messages in thread From: Marin David Condic @ 2002-05-03 13:04 UTC (permalink / raw) Yeah, but in effect that's just generating random permutations of the data instead of ordered permutations. If you want to guarantee that you actually end up with an answer, you have to do something with your PRNG that makes sure it would generate all permutations, so, on average it would perform the same as generating ordered permutations. A better (slower) algorithm would be to generate a random set of machine instructions, execute them, see if it sorted the list and quit when it does. The problem, of course, is that you can't guarantee that it will ever finish. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com "Mark Biggar" <mark.a.biggar@attbi.com> wrote in message news:3CD1664A.804F56BC@attbi.com... > > There are worse sorts then Bogosort. For example there is 52-pickup > sort: repeatedly randomize the list until you notice that it > is sorted. > ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-03 13:04 ` Marin David Condic @ 2002-05-05 0:52 ` Robert Dewar 2002-05-05 23:11 ` tmoran ` (2 more replies) 0 siblings, 3 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-05 0:52 UTC (permalink / raw) "Marin David Condic" > A better (slower) algorithm would be > to generate a random set of machine > instructions, execute them, see if it sorted the list ^^^ You could see if it sorted some particular list, but to determine whether a set of instructions constitutes a general sorting algorithm is obviously recursively undecidable. So this is not a well formed method. Incidentally while we are at it, consider the following sorting algorithm which is guaranteed to do the minimal number of comparisons under all circumstances: Step 1. Determine number of items to be sorted Step 2. Enumerate all binary decision trees for sorting this number of items. Step 3. Choose the decision tree with the minimum depth Step 4. Use this tree to sort the data ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-05 0:52 ` Robert Dewar @ 2002-05-05 23:11 ` tmoran 2002-05-06 2:13 ` Chad R. Meiners 2002-05-06 21:33 ` Robert Dewar 2002-05-06 17:26 ` Marin David Condic 2002-05-07 7:35 ` tmoran 2 siblings, 2 replies; 88+ messages in thread From: tmoran @ 2002-05-05 23:11 UTC (permalink / raw) > but to determine whether a set of instructions constitutes a general > sorting algorithm is obviously recursively undecidable. So the set of instructions emitted by Gnat when it compiles bubble sort code may or may not constitute a general sorting algorithm, and whether it does or not is undecidable? I learn something new every day. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-05 23:11 ` tmoran @ 2002-05-06 2:13 ` Chad R. Meiners 2002-05-06 13:52 ` Stephen Leake 2002-05-06 15:46 ` Wes Groleau 2002-05-06 21:33 ` Robert Dewar 1 sibling, 2 replies; 88+ messages in thread From: Chad R. Meiners @ 2002-05-06 2:13 UTC (permalink / raw) No that is not what Robert was saying. He was referring to Rice's Theorem for which you can clearly show that the problem of determining whether a given set of machine instructions will sort an given input is Turing-undecidable. How did you come to such a misinterpretation? <tmoran@acm.org> wrote in message news:p_iB8.3409$9d1.36389081@newssvr21.news.prodigy.com... > > but to determine whether a set of instructions constitutes a general > > sorting algorithm is obviously recursively undecidable. > So the set of instructions emitted by Gnat when it compiles bubble sort > code may or may not constitute a general sorting algorithm, and whether > it does or not is undecidable? I learn something new every day. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-06 2:13 ` Chad R. Meiners @ 2002-05-06 13:52 ` Stephen Leake 2002-05-09 17:44 ` Darren New 2002-05-06 15:46 ` Wes Groleau 1 sibling, 1 reply; 88+ messages in thread From: Stephen Leake @ 2002-05-06 13:52 UTC (permalink / raw) "Chad R. Meiners" <crmeiners@hotmail.com> writes: > No that is not what Robert was saying. He was referring to Rice's Theorem > for which you can clearly show that the problem of determining whether a > given set of machine instructions will sort an given input is > Turing-undecidable. How did you come to such a misinterpretation? Doesn't sound like a "misinterpretation" to me. Let's try some symbolic logic: A : "a given set of machine instructions" B : "a given input" C : A sorts B Rice's Theorem says statement C is "Turing-undecideable". Question; does that mean C is "false"? A' : "set of instructions emitted by GNAT for bubble sort" B' : "a given input" C' : A' sorts B' So Rice's Theorem says statement C' is "Turing-undecideable". Is C' "true"? If C' is "true", does that mean A' "constitutes a general sorting algorithm". I think so, if we assume B' is allowed to vary over all possible inputs. I suspect the problem here lies in the conflict between the English meanings of "true" and "decideable", and the formal meaning of "Turing-(un)decideable". We all believe that C' is "true", but that's not the same as "Turing-decideable". I'll leave it to someone else to give the formal definition of "Turing-decideable"; I'm sure I'd get it wrong :). > > > <tmoran@acm.org> wrote in message > news:p_iB8.3409$9d1.36389081@newssvr21.news.prodigy.com... > > but > to determine whether a set of instructions constitutes a general > > > sorting algorithm is obviously recursively undecidable. > So the set > of instructions emitted by Gnat when it compiles bubble sort > code > may or may not constitute a general sorting algorithm, and whether > > it does or not is undecidable? I learn something new every day. > > -- -- Stephe ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-06 13:52 ` Stephen Leake @ 2002-05-09 17:44 ` Darren New 2002-05-09 18:07 ` Stephen Leake 0 siblings, 1 reply; 88+ messages in thread From: Darren New @ 2002-05-09 17:44 UTC (permalink / raw) Stephen Leake wrote: > > "Chad R. Meiners" <crmeiners@hotmail.com> writes: > > > No that is not what Robert was saying. He was referring to Rice's Theorem > > for which you can clearly show that the problem of determining whether a > > given set of machine instructions will sort an given input is > > Turing-undecidable. How did you come to such a misinterpretation? > > Doesn't sound like a "misinterpretation" to me. > > Let's try some symbolic logic: > > A : "a given set of machine instructions" > B : "a given input" > C : A sorts B > > Rice's Theorem says statement C is "Turing-undecideable". > > Question; does that mean C is "false"? No, it means that you can't write a program that runs on a turing machine that will invariably decide in finite time whether C is true or not. C isn't false, it's undecidable. It's right there in the word. :-) Note that "undecidable" isn't talking about A or B or C as such. It's more talking about a program that *looks* at As and Bs and decides whether C is true. > A' : "set of instructions emitted by GNAT for bubble sort" > B' : "a given input" > C' : A' sorts B' > > So Rice's Theorem says statement C' is "Turing-undecideable". Yes. You have to understand that if you limit "A" to be "a set of instructions emitted by GNAT for bubble sort" then the question goes away. You can just write a program that outputs "true" without even looking at the inputs, and you'll be giving the right answer. But that same program won't work if you give it a different A'', which is a set of instructions emitted by GNAT for generating a random permutation of B''. It's the difference between asking "does this program sort the list" and "does this sort program sort the list". Of course the sort program sorts the list, because you told me it's a sort program. It's kind of like the difference between Big-O and Big-Theta in performance. Does a bubble sort run in O(N**2)? Yep. Can you sort faster? You can't tell just by looking at bubble sorts. No matter how many algorithms you look at, you'll never figure out if you've found the fastest one. You have to look at the *problem* to decide if you've found the fastest algorithm. > Is C' "true"? Yes, but irrelevant. > If C' is "true", does that mean A' "constitutes a general sorting > algorithm". I think so, if we assume B' is allowed to vary over all > possible inputs. Right. So? The question is not whether it's possible to look at one program and decide what it does. The question is whether it's possible to write a program to look at all programs and decide whether or not they sort. > I suspect the problem here lies in the conflict between the English > meanings of "true" and "decideable", and the formal meaning of > "Turing-(un)decideable". We all believe that C' is "true", but that's > not the same as "Turing-decideable". "Turing undecidable" means basically that there's no program you can write for a turing machine that given as input A will tell you whether C is true for all B's, if said turing machine program has to always be right and has to always finish in a finite amount of time. Of course for any *one* A you can decide this, but that's irrelevant because that program will not work on some sort that isn't A. Put it this way. Does the following program calculate square roots? Put_Line("5"); Well, if the input is 25, then yes, it calculates square roots. That's a simplification of the logic you're sort of applying there - sure, that a sort program sorts a list can be proven, but that's not what "sorting is undecidable" means. If sorting were decidable, it would be possible to look at any program and figure out reliably whether it sorts or not. Try this one: A": A buggy bubblesort that sorts B as long as the biggest value doesn't start at the beginning of the list. B": A list of numbers with the biggest value already in the middle C": Does A" sort B"? Well, yes, but again, irrelevant for exactly the same reason. No, A" isn't a general sort because it doesn't work when B" is different. For the same reason, sorting isn't decidable because your program to decide whether its a general sort gives the wrong answer when A' is a different program. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 17:44 ` Darren New @ 2002-05-09 18:07 ` Stephen Leake 2002-05-09 20:58 ` Darren New ` (2 more replies) 0 siblings, 3 replies; 88+ messages in thread From: Stephen Leake @ 2002-05-09 18:07 UTC (permalink / raw) Darren New <dnew@san.rr.com> writes: > Right. So? The question is not whether it's possible to look at one > program and decide what it does. The question is whether it's possible > to write a program to look at all programs and decide whether or not > they sort. That's _your_ question. The question _I_ was addressing, as posed by TMoran, was "Is the sequence of instructions emitted by GNAT when it compiles bubble sort a program that sorts it's input". You have to be careful in newsgroup discussions to pay attention to the question the poster is asking, and not assume they are talking about what you are talking about ! > > I suspect the problem here lies in the conflict between the > > English meanings of "true" and "decideable", and the formal > > meaning of "Turing-(un)decideable". We all believe that C' is > > "true", but that's not the same as "Turing-decideable". > > "Turing undecidable" means basically that there's no program you can > write for a turing machine that given as input A will tell you whether C > is true for all B's, if said turing machine program has to always be > right and has to always finish in a finite amount of time. Of course for > any *one* A you can decide this, but that's irrelevant because that > program will not work on some sort that isn't A. Ok. So what Tom Moran and I were missing was the notion that A _must_ be allowed to vary over _all_ instruction sequences, not just _a particular_ instruction sequence. That's an extremely important distinction, and it was _not_ clear in Robert's original post, although I can see how he thought it was implied. > Put it this way. Does the following program calculate square roots? > Put_Line("5"); > > Well, if the input is 25, then yes, it calculates square roots. > > That's a simplification of the logic you're sort of applying there - Actually, the correct analogy to what I'm saying is "Does the following program find the square root of 25?". I agree that this is a trivial question. That's why Tom Moran was surprised at Robert's response. (we are way lost in he said/she said at this point :). -- -- Stephe ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 18:07 ` Stephen Leake @ 2002-05-09 20:58 ` Darren New 2002-05-09 23:21 ` tmoran 2002-05-25 16:21 ` Robert I. Eachus 2002-05-09 23:24 ` Robert Dewar 2002-05-09 23:48 ` Robert Dewar 2 siblings, 2 replies; 88+ messages in thread From: Darren New @ 2002-05-09 20:58 UTC (permalink / raw) Stephen Leake wrote: > > Darren New <dnew@san.rr.com> writes: > > > Right. So? The question is not whether it's possible to look at one > > program and decide what it does. The question is whether it's possible > > to write a program to look at all programs and decide whether or not > > they sort. > > That's _your_ question. The question _I_ was addressing, as posed by > TMoran, was "Is the sequence of instructions emitted by GNAT when it > compiles bubble sort a program that sorts it's input". Well, I was addressing the "misinterpretation" claim. I don't think anyone claimed that the instructions emitted by compiling a bubble sort don't sort the list. I thought TMoran was saying that he was surprised that sorting was recursively undecidable since he can prove a bubble sort does indeed sort. But that's not what "recursively undecidable" means. I was addressing this: -------- > > but to determine whether a set of instructions constitutes a general > > sorting algorithm is obviously recursively undecidable. > So the set of instructions emitted by Gnat when it compiles bubble sort > code may or may not constitute a general sorting algorithm, and whether > it does or not is undecidable? I learn something new every day. --------- That's a misinterpretation of what "general sorting algorithm" and "recursively undecidable" means. Hence, that you're asking a different question is kind of ... irrelevant, and therefore not addressed. Everything you said was correct, except for any implication that it relates to undecidability. > You have to be careful in newsgroup discussions to pay attention to > the question the poster is asking, and not assume they are talking > about what you are talking about ! Well, you said "it doesn't sound like a misinterpretation to me". I was explaining how the second part of the quote between the lines there is a misinterpretation of the first part. > Ok. So what Tom Moran and I were missing was the notion that A _must_ > be allowed to vary over _all_ instruction sequences, not just _a > particular_ instruction sequence. That's an extremely important > distinction, and it was _not_ clear in Robert's original post, > although I can see how he thought it was implied. Correct. It's easy to prove that (say) a bubble sort does indeed sort. It's impossible to reliably determine if a given set of instructions (i.e., one given to you, not one chosen by you) does indeed sort an arbitrary list of numbers. "A given set of instructions" means whatever set I give you, not one that you get to pick. This is normal math-speak, so I'm not surprised that it was considered implied. Consider function square(a : double) return double is return a * a; end square; -- (assuming I got the syntax right) This "squares a given number". I.e., it squares whatever number you give it. If it doesn't work for any number you give it, then it doesn't "square a given number", at least in normal math-speak. > I agree that this is a trivial question. That's why Tom Moran was > surprised at Robert's response. (we are way lost in he said/she said > at this point :). I think so. I think the original point was that a slow-sort can't be implemented by generating random instruction sets until you find one that is a sort program, because you can't tell if any arbitrary randomly-generated set of instructions is a sort or not. Sure, if you design the code to be a sort, you can tell it's a sort, and even prove it's a sort, but you can't generate programs at random and say anything in particular about them. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 20:58 ` Darren New @ 2002-05-09 23:21 ` tmoran 2002-05-09 23:51 ` Darren New 2002-05-25 16:21 ` Robert I. Eachus 1 sibling, 1 reply; 88+ messages in thread From: tmoran @ 2002-05-09 23:21 UTC (permalink / raw) > It's impossible to [always] reliably determine if a given set of instructions > (i.e., one given to you, not one chosen by you) does indeed sort an > arbitrary list of numbers. With the word "always" that's true. Without that word it's false. There do exist sets of instructions that can be reliably determined to sort an/any arbitrary *finite* list of numbers. (I suspect, but haven't proved, that the aforementioned output of Gnat is one such set of instructions.) (I don't know what it might mean to "sort an infinite list".) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 23:21 ` tmoran @ 2002-05-09 23:51 ` Darren New 2002-05-10 3:37 ` tmoran 0 siblings, 1 reply; 88+ messages in thread From: Darren New @ 2002-05-09 23:51 UTC (permalink / raw) tmoran@acm.org wrote: > > > It's impossible to [always] reliably determine if a given set of instructions > > (i.e., one given to you, not one chosen by you) does indeed sort an > > arbitrary list of numbers. > With the word "always" that's true. Without that word it's false. If I give you a set of instructions, it's impossible for you to reliably determine if that set of instructions implements a sort. "Reliably" implies "always", doesn't it? I mean, if I give you a block of instructions and ask "does this implement a sort", and sometimes you can say "Yes, I'm sure it does", and sometimes you can only say "I can't tell", then doesn't that mean your program doesn't reliably give the right answer? Again, we're talking about the method of figuring out whether it's a sort that's reliable, not whether the program itself sorts correctly. Your program doesn't reliably calculate square roots if it only works for the number 25 either - it has to work for all inputs in the domain. I mean, my car starts very reliably, except when it doesn't. That doesn't make any sense. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 23:51 ` Darren New @ 2002-05-10 3:37 ` tmoran 2002-05-10 3:59 ` Darren New 2002-05-10 13:13 ` Robert Dewar 0 siblings, 2 replies; 88+ messages in thread From: tmoran @ 2002-05-10 3:37 UTC (permalink / raw) > determine if that set of instructions implements a sort. "Reliably" > implies "always", doesn't it? I mean, if I give you a block of > instructions and ask "does this implement a sort", and sometimes you can > say "Yes, I'm sure it does", and sometimes you can only say "I can't > tell", then doesn't that mean your program doesn't reliably give the > right answer? This is almost as bad as philosophy in terms of one person thinking, erroneously, that another person interprets a statement the same way. To me, "reliably" does not imply "always". It simply implies that it never gives a *wrong* answer. A time traveler from the future might be totally reliable when he predicts the outcome of a presidential election, but he might not know, and thus wouldn't tell me, if the penny I'm tossing will come up heads. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-10 3:37 ` tmoran @ 2002-05-10 3:59 ` Darren New 2002-05-10 13:13 ` Robert Dewar 1 sibling, 0 replies; 88+ messages in thread From: Darren New @ 2002-05-10 3:59 UTC (permalink / raw) tmoran@acm.org wrote: > To me, "reliably" does not imply "always". It simply implies that > it never gives a *wrong* answer. Well, not giving any answer at all is a wrong answer. Otherwise, the program that consists of while (1) {} will be a very reliable program for every purpose, which is counterintuitive. It's also a wrong answer by the nature of the definition of "recursive undecidability", if you care to talk about formal definitions for terminology. In any case, considering that the original message was talking about "recursive undecidability", a simple google on that phrase would have revealed exactly what was meant. And this thread has probably gone on waaaaay too long, so if we're just going to continue with "I thought" / "you thought" etc, it's not worthwhile for me to answer. You may have the last word. :-) -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-10 3:37 ` tmoran 2002-05-10 3:59 ` Darren New @ 2002-05-10 13:13 ` Robert Dewar 1 sibling, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-10 13:13 UTC (permalink / raw) tmoran@acm.org wrote in message news:<PfHC8.578$To4.77821283@newssvr14.news.prodigy.com>... > To me, "reliably" does not imply "always". It simply implies that > it never gives a *wrong* answer. Hmmm! Humpty-Dumpty is busy today :-) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 20:58 ` Darren New 2002-05-09 23:21 ` tmoran @ 2002-05-25 16:21 ` Robert I. Eachus 1 sibling, 0 replies; 88+ messages in thread From: Robert I. Eachus @ 2002-05-25 16:21 UTC (permalink / raw) Darren New wrote: > "A given set of instructions" means whatever set I give you, not one > that you get to pick. This is normal math-speak, so I'm not surprised > that it was considered implied. Consider > > function square(a : double) return double is return a * a; end square; > -- (assuming I got the syntax right) > > This "squares a given number". I.e., it squares whatever number you give > it. If it doesn't work for any number you give it, then it doesn't > "square a given number", at least in normal math-speak. Wow! What a fascinating question: For what Ada types "double" does this actually provide the square of a number? Another related question is whether it returns the correct value or raises an exception. Not true for all integer types, but true for type Double is range 0..1; If you use the looser definition, then true for all integer types. True for all modular types. Modular values do not have unique square roots, but that is a normal property of squares. All modular types are closed under multiplication, and will never result in an exception. (With Storage_Error always a possibility, but an uninteresting one.) False in both senses for floating-point types. There are values which will result in IEEE infinities or overflow. (Underflow is not possible.) But for only a small subset of the representable real values is the square also exactly representable. For fixed-point types, the question gets really hairy. There are trivial fixed point types for which it is true. For other fixed-point types, the multiplication returns the correct result, but rounding or truncation can occur on the implicit conversion to double. This will not occur for 'SMALLs which are a multiple of 1.0. The implicit assignment in the return statement may raise Contraint_Error, but for which ranges? Constraint_Error will not be raised for null ranges, for the range 0.0..0.0, for ranges of -1.0..1.0, and ranges of the form X..1.0 for X non-negative. However, there is a special case to be aware of. For types with an upper bound of 1.0, or with a declaration of the form type double is range N..1.0 - M delta M, it is possible for double'Last * double'Last to raise Constraint_Error. This can also occur for x * x when x = -1.0 even if double'last is 1.0. I'm not even going to touch complex types from the Numerics Annex. ;-) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 18:07 ` Stephen Leake 2002-05-09 20:58 ` Darren New @ 2002-05-09 23:24 ` Robert Dewar 2002-05-09 23:48 ` Robert Dewar 2 siblings, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-09 23:24 UTC (permalink / raw) Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message news:<uwuud2o12.fsf@gsfc.nasa.gov>... > That's why Tom Moran was surprised at Robert's response. > (we are way lost in he said/she said at this point :) Hmmm! I rather thin that the reason Tom Moran got confused and surprised was that he did not know what recursively undecidable meant :-). I am not one to think that all practicing programmers need extension knowledge of theoretical computer science but I do think that everyone should have the basic notions of Turing decidability and NP completeness in their vocabulary ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 18:07 ` Stephen Leake 2002-05-09 20:58 ` Darren New 2002-05-09 23:24 ` Robert Dewar @ 2002-05-09 23:48 ` Robert Dewar 2002-05-10 3:37 ` tmoran 2002-05-10 15:10 ` Chad R. Meiners 2 siblings, 2 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-09 23:48 UTC (permalink / raw) Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message news:<uwuud2o12.fsf@gsfc.nasa.gov>... > Darren New <dnew@san.rr.com> writes: > >> Right. So? The question is not whether it's possible to >> look at one program and decide what it does. The >> question is whether it's possible to write a program to >> look at all programs and decide whether or not they sort > > That's _your_ question. The question _I_ was addressing, > as posed by TMoran, was "Is the sequence of instructions > emitted by GNAT when it compiles bubble sort a program > that sorts it's input". But that's an entirely trivial question, if you thin anyone was addressing that or interest in that, you were confused. Of course the sequence of instructions generated by GNAT for bubble sort is provably a general sorting algorithm. That cannot be in question (if anyone questions that they are really really confused :-) Here is the actual Tom Moran quote: Robert: > but to determine whether a set of instructions > constitutes a general sorting algorithm is obviously > recursively undecidable. Tom: > So the set of instructions emitted by Gnat when it > compiles bubble sort code may or may not constitute a > general sorting algorithm, and whether it does or not is > undecidable? Now it is (I trust :-) so completely obvious that you can prove that the output of GNAT when it compile bubble sort is indeed a general sorting algorithm. We can't for a moment assume that Tom *really* thinks that it is undecidable :-) So the only reading of Tom's message is an attempt to disprove what I wrote by example. In other words he thinks my statement was implying the obviously incorrect conclusion. But that's where the misunderstanding crept in, because of course what I said does NOT imply this Assuming that anyone not interested in this has long ago killed this thread, let's take another stab at clarifying this issue. As I said earlier, the placement of quantifies is absolutely crucial. At the risk of boring everyone, let's persue this: The following statement is true: For any sequence of code that does NOT constitute a general sorting algorithm, there is a trivial proof that it does not constitute swuch an algorithm (namely a counter example). The following statement is true For any particular sequence of code, there is an algorithm that determines whether or not this sequence of code is or is not a general sorting algorithm (trivially true, the answer is Yes or No :-) The following statement is true There is NO general algorithm, which when presented with a particular sequence of code as input, can determine whether or not the piece of code is a general sorting algorithm. Understanding why all three statements are true is instructive :-) The first two statements are trivially true, and once you understand them, you should be able to immediately see that they are true. To see that the third statement is true is non-trivial. To prove this, we assume the halting problem and then prove by equivalence to this problem. Let's take a bubble sort and in the middle of it, run some arbitrary Turing machine till it halts. But now the general algorithm will have to be able to determine if it halts (algorithm is a good sort) or does not halt (algorithm is junk, runs for ever). The proof of the undecidability of the halting problem can be found in any book on computability. It's not that difficult to follow, but too much to outline here. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 23:48 ` Robert Dewar @ 2002-05-10 3:37 ` tmoran 2002-05-10 15:10 ` Chad R. Meiners 1 sibling, 0 replies; 88+ messages in thread From: tmoran @ 2002-05-10 3:37 UTC (permalink / raw) > > but to determine whether a set of instructions > > So the set of instructions emitted by Gnat when it > >sort is indeed a general sorting algorithm. We can't for > >a moment assume that Tom *really* thinks that it is undecidable :-) > > So the only reading of Tom's message is an attempt to > disprove what I wrote by example. Another reading is that Tom foolishly left off the smiley when he tried to point out that things must be stated more carefully, and in particular, "a" set of instructions is different from "any" set of instructions, and if "a" had really been meant, then the statement would imply, for instance, that when "a set of instructions" happened to be the particular "set of instructions emitted by Gnat...", the sort couldn't be proved to work. Tom assumed that reader's of the message would not assume someone was ignorant of, or attempting to disprove by example, undecidability. Tom assumed wrong. ("Know your audience" & "Don't leave off smileys")**100 ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-09 23:48 ` Robert Dewar 2002-05-10 3:37 ` tmoran @ 2002-05-10 15:10 ` Chad R. Meiners 2002-05-11 4:04 ` Robert Dewar 2002-05-11 4:05 ` Robert Dewar 1 sibling, 2 replies; 88+ messages in thread From: Chad R. Meiners @ 2002-05-10 15:10 UTC (permalink / raw) "Robert Dewar" <dewar@gnat.com> wrote in message news:5ee5b646.0205091548.cd99d4c@posting.google.com... > To prove this, we assume the halting problem and then > prove by equivalence to this problem. Let's take a > bubble sort and in the middle of it, run some arbitrary > Turing machine till it halts. But now the general > algorithm will have to be able to determine if it > halts (algorithm is a good sort) or does not halt > (algorithm is junk, runs for ever). I just wanted you correct an error in this informal proof. The proof should go like this. Assume the existence of Is_Sort(x) (The program that decides if x is a general sorting algorithm) We can construct Halt(Y,Z) (The program that decides if program Y halt on input Z) as follows Build a machine x'(w) such that x' runs Y(Z) and then runs a bubble sort on w. run Is_Sort(x') return true if x' is a sorting algorithm return false if x' is not a sorting algorithm end of Halt Thus Halt is decidable But Halt is undecidable thus contradiction Ergo, Is_Sort cannot exist. Is_Sort is undecidable. You should note that Robert's proof is in essence correct except that he assumes that the wrong machine exists. This could have easily been a typo but a very grievous one at that since the entire proof depends upon the correct assumption. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-10 15:10 ` Chad R. Meiners @ 2002-05-11 4:04 ` Robert Dewar 2002-05-16 1:35 ` Chad R. Meiners 2002-05-11 4:05 ` Robert Dewar 1 sibling, 1 reply; 88+ messages in thread From: Robert Dewar @ 2002-05-11 4:04 UTC (permalink / raw) "Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<abgnvp$1u9q$1@msunews.cl.msu.edu>... > "Robert Dewar" <dewar@gnat.com> wrote in message > news:5ee5b646.0205091548.cd99d4c@posting.google.com... > > To prove this, we assume the halting problem and then > > prove by equivalence to this problem. Let's take a > > bubble sort and in the middle of it, run some arbitrary > > Turing machine till it halts. But now the general > > algorithm will have to be able to determine if it > > halts (algorithm is a good sort) or does not halt > > (algorithm is junk, runs for ever). > > I just wanted you correct an error in this informal proof. The proof should > go like this. I see no error in the proof, you are somehow misreading what I wrote. Perhaps you misunderstand my short hand. When I say "assume the halting problem", I mean "assume that we have already shown that the halting problem for Turing Machines is undecidable". Was that your problem? I really can't understand your problem otherwise? The informal proof above is exactly correct, and seems quite clear to me, so if it does not seem clear to you, you are misreading it. > > Assume the existence of Is_Sort(x) (The program that decides if x is a > general sorting algorithm) > > We can construct Halt(Y,Z) (The program that decides if program Y halt on > input Z) as follows > > Build a machine x'(w) such that x' runs Y(Z) and then runs a bubble sort on > w. > > run Is_Sort(x') > > return true if x' is a sorting algorithm > return false if x' is not a sorting algorithm > > end of Halt > > Thus Halt is decidable > But Halt is undecidable thus contradiction > Ergo, Is_Sort cannot exist. > Is_Sort is undecidable. > > You should note that Robert's proof is in essence correct except that he > assumes that the wrong machine exists. This could have easily been a typo > but a very grievous one at that since the entire proof depends upon the > correct assumption. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-11 4:04 ` Robert Dewar @ 2002-05-16 1:35 ` Chad R. Meiners 0 siblings, 0 replies; 88+ messages in thread From: Chad R. Meiners @ 2002-05-16 1:35 UTC (permalink / raw) Sorry for the delayed response; I was away. "Robert Dewar" <dewar@gnat.com> wrote in message news:5ee5b646.0205102004.6142053c@posting.google.com... > I see no error in the proof, you are somehow misreading what I wrote. Perhaps > you misunderstand my short hand. When I say "assume the halting problem", I > mean "assume that we have already shown that the halting problem for Turing > Machines is undecidable". Was that your problem? No, your proof has a logical error in it along with its the language ambiguity. It doesn't existablish proof of equivalance nor does it prove that Is_Sort is undecidable. It fails to prove that Is_Sort might exist without needing to depend upon the halting problem. This is why we must assume that Is_Sort is decidable and show that this leads to a contradiction. > I really can't understand your problem otherwise? > > The informal proof above is exactly correct, and seems quite clear to me, so > if it does not seem clear to you, you are misreading it. While I am sure you understand why Is_Sort is undecidable, you have gone about proving it incorrectly. You might argue that there is enough reasoning within your argument for anyone to "see" why it is correct. For someone that is willing to believe your proof, this argument might suffice, but a skeptic would raise the problem I mentioned above. The skeptic, however, cannot argue with my proof by contradiction because it leaves no room to argue. Please note that I was not saying that you are completely off the mark, but instead that you were not careful in your proof and made in an error that anyone might have made since the error is not obvious. -CRM ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-10 15:10 ` Chad R. Meiners 2002-05-11 4:04 ` Robert Dewar @ 2002-05-11 4:05 ` Robert Dewar 1 sibling, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-11 4:05 UTC (permalink / raw) "Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<abgnvp$1u9q$1@msunews.cl.msu.edu>... > You should note that Robert's proof is in essence correct except that he > assumes that the wrong machine exists. I assume nothing of the kind, this is some kind of language problem or other misunderstanding of what I wrote, which was a simple equivalence proof (the is-a-sort predicate is undecidable if the halting-problem is undecidable). ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-06 2:13 ` Chad R. Meiners 2002-05-06 13:52 ` Stephen Leake @ 2002-05-06 15:46 ` Wes Groleau 2002-05-06 16:21 ` Chad R. Meiners 2002-05-06 16:33 ` Darren New 1 sibling, 2 replies; 88+ messages in thread From: Wes Groleau @ 2002-05-06 15:46 UTC (permalink / raw) > > > but to determine whether a set of instructions constitutes a general > > > sorting algorithm is obviously recursively undecidable. > > So the set of instructions emitted by Gnat when it compiles bubble sort > > code may or may not constitute a general sorting algorithm, and whether > > it does or not is undecidable? I learn something new every day. > > No that is not what Robert was saying. He was referring to Rice's Theorem > for which you can clearly show that the problem of determining whether a > given set of machine instructions will sort an given input is > Turing-undecidable. How did you come to such a misinterpretation? "given set of machine instructions" => "instructions emitted by Gnat when it compiles bubble sort" "determining whether ... will sort an given input " => "may or may not constitute a general sorting algorithm" What did I miss ? -- Wes Groleau http://freepages.rootsweb.com/~wgroleau ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-06 15:46 ` Wes Groleau @ 2002-05-06 16:21 ` Chad R. Meiners 2002-05-06 16:33 ` Darren New 1 sibling, 0 replies; 88+ messages in thread From: Chad R. Meiners @ 2002-05-06 16:21 UTC (permalink / raw) "Wes Groleau" <wesgroleau@despammed.com> wrote in message news:3CD6A550.6C8AE20F@despammed.com... > What did I miss ? I am unsure ;-) but I was only stating that the problem (a) of taking a set of instructions and translating them to a different set(compiling) is very different from the problem (b) of determining the equivalence of two sets of instructions. Robert was talking about problem (b) while Tom was talking about problem (a). This was the misunderstanding. -CRM ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-06 15:46 ` Wes Groleau 2002-05-06 16:21 ` Chad R. Meiners @ 2002-05-06 16:33 ` Darren New 2002-05-07 0:06 ` tmoran 1 sibling, 1 reply; 88+ messages in thread From: Darren New @ 2002-05-06 16:33 UTC (permalink / raw) Wes Groleau wrote: > "given set of machine instructions" => > "instructions emitted by Gnat when it compiles bubble sort" I think that what you missed is the implication behind how it was phrased. "Given a set of machine instructions" is generally taken to mean "given any arbitrary set of machine instructions" by folks who talk about things like "sets of machine instructions". So "instructions emitted by Gnat when it compiles a bubble sort" doesn't count, because you're already assuming you know it's a bubble sort. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-06 16:33 ` Darren New @ 2002-05-07 0:06 ` tmoran 2002-05-07 0:26 ` Darren New 0 siblings, 1 reply; 88+ messages in thread From: tmoran @ 2002-05-07 0:06 UTC (permalink / raw) > ... is generally taken to mean ... by folks who ... The First Commandment to a writer is "Know your audience". Phrases with an idiosyncratic meaning to one audience are just confusing when directed to different audiences. > So "instructions emitted by Gnat when it compiles a bubble sort" doesn't > count, because you're already assuming you know it's a bubble sort. Prof to students: "Here is a set of machine instructions in the form of Ada source code. What do they do? Prove it." Poor students: "How the heck should I know?" Medium students: "It's a bubble sort, and here's a proof that it works." Good students: "How the heck could I know?" ? ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 0:06 ` tmoran @ 2002-05-07 0:26 ` Darren New 2002-05-07 1:56 ` tmoran 2002-05-07 17:00 ` Wes Groleau 0 siblings, 2 replies; 88+ messages in thread From: Darren New @ 2002-05-07 0:26 UTC (permalink / raw) tmoran@acm.org wrote: > > > ... is generally taken to mean ... by folks who ... > The First Commandment to a writer is "Know your audience". Phrases > with an idiosyncratic meaning to one audience are just confusing when > directed to different audiences. The First Commandment to a newsgroup reader is "if you don't understand it, try google." Somehow, tho, I thought that any software engineer would have had at least one class about computability (or at least formal mathematics) and would therefore have recognised the form of the statement. If you don't recognise "a given set of machine instructions" as meaning any arbitrary set of programs then, well, I guess you haven't studied much formally. > Prof to students: "Here is a set of machine instructions in the form of > Ada source code. What do they do? Prove it." > Poor students: "How the heck should I know?" > Medium students: "It's a bubble sort, and here's a proof that it works." > Good students: "How the heck could I know?" But that's not the question. The question is "write a program that tells whether the input to that program is another program that will sort the list." The question isn't "does program X sort the list", but rather "does program Y reliably tell you that program X sorts a list, for any program X." How about this: Take the output from SHA-1 hashing a counter. Arrange the list in the order indicated by the result of the hash. Check to see if it's sorted, and halt if it is. Does that ever sort the list? Good students: "How the heck could I know?" The original comment was > to determine whether a set of instructions constitutes a > general sorting algorithm is obviously recursively > undecidable If you don't understand that sentence, then why argue with people who explain it to you? If "recursively undecidable" doesn't mean anything to you, then arguing that "a given set of instructions" is unintuitive is foolish. Implicit in the meaning of "recursively undecidable" is the quantifier in front of "a set of instructions." You asked what you're missing, and when you're told that, you argue that ... what, you shouldn't have missed it? Or that the person telling you what you missed is wrong? Or that since you're more ignorant than the Robert about the subject, he should educate you before pointing out your mistake? -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 0:26 ` Darren New @ 2002-05-07 1:56 ` tmoran 2002-05-07 10:39 ` Robert Dewar 2002-05-07 17:00 ` Wes Groleau 1 sibling, 1 reply; 88+ messages in thread From: tmoran @ 2002-05-07 1:56 UTC (permalink / raw) > If you don't recognise "a given set of machine instructions" as meaning > any arbitrary set of programs ... Perhaps such newsgroup posts should follow Knuth's problem sets and start with a difficulty/requires higher mathematics/non-English phrase meanings indicator. Or perhaps the "From:" line does the job. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 1:56 ` tmoran @ 2002-05-07 10:39 ` Robert Dewar 2002-05-07 17:25 ` Chad R. Meiners 0 siblings, 1 reply; 88+ messages in thread From: Robert Dewar @ 2002-05-07 10:39 UTC (permalink / raw) tmoran@acm.org wrote in message news:<pvGB8.6211$n26.84235643@newssvr21.news.prodigy.com>... > > If you don't recognise "a given set of machine instructions" as meaning > > any arbitrary set of programs ... > Perhaps such newsgroup posts should follow Knuth's problem sets and > start with a difficulty/requires higher mathematics/non-English phrase > meanings indicator. Or perhaps the "From:" line does the job. Really this is not "higher mathematics", but it is the sort of thing you learn in a course about formal computation (Turing machines etc). The phrase "recursively undecidable" should be a tip off that we are in that realm :-) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 10:39 ` Robert Dewar @ 2002-05-07 17:25 ` Chad R. Meiners 2002-05-08 2:27 ` Robert Dewar 2002-05-08 8:44 ` Mats Karlssohn 0 siblings, 2 replies; 88+ messages in thread From: Chad R. Meiners @ 2002-05-07 17:25 UTC (permalink / raw) "Robert Dewar" <dewar@gnat.com> wrote in message news:5ee5b646.0205070239.77c6bac2@posting.google.com... > tmoran@acm.org wrote in message news:<pvGB8.6211$n26.84235643@newssvr21.news.prodigy.com>... > The phrase "recursively undecidable" should be a tip off that we are > in that realm :-) Actually I am interested where you picked up the phrase "recursively undecidable". A better phrase would be "not recursive" since we are referring to recursive languages. Perhaps it is simply a hybridization of "Turing-decidable" and "recursive" since it would be harmless enough to merge two equivalent phrases. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 17:25 ` Chad R. Meiners @ 2002-05-08 2:27 ` Robert Dewar 2002-05-08 8:44 ` Mats Karlssohn 1 sibling, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-08 2:27 UTC (permalink / raw) > Actually I am interested where you picked up the phrase > "recursively undecidable". A better phrase would be "not > recursive" since we are referring to recursive languages. It's a very standard phrase in my vocabulary. And I did not invent it. To pick up one quick reference from many, the following is the statement of Richardson's Theorem from Eric Weisstein's world of mathematics: Let R be the class of expressions generated by 1. The rational numbers and the two real numbers pi and ln 2, 2. The variable x, 3. The operations of addition, multiplication, and composition, and 4. The sine, exponential, and absolute value functions. Then if E in R, the predicate "E = 0" is recursively undecidable. (I must say this thread has gone splendidly off topic, even for CLA :-) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 17:25 ` Chad R. Meiners 2002-05-08 2:27 ` Robert Dewar @ 2002-05-08 8:44 ` Mats Karlssohn 1 sibling, 0 replies; 88+ messages in thread From: Mats Karlssohn @ 2002-05-08 8:44 UTC (permalink / raw) "Chad R. Meiners" wrote: %< > Actually I am interested where you picked up the phrase "recursively > undecidable". A better phrase would be "not recursive" since we are > referring to recursive languages. Perhaps it is simply a hybridization of > "Turing-decidable" and "recursive" since it would be harmless enough to > merge two equivalent phrases. As far as I can tell, "recursively undecidable" is part of the standard terminology used by logicans and mathematical philosofers. I first heard the term used (and got it explained) during my first university course in mathematical philosophy. How ever this is kind of an interpolation since the course was (of cource ;-) held in swedish. I didn't actually see the english term until later during my first course in logic. -- Mats Karlssohn, developer mailto:mats@mida.se Mida Systemutveckling AB http://www.mida.se Box 64, S-732 22 ARBOGA, SWEDEN Phone: +46-(0)589-89808 Fax: +46-(0)589-89809 ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 0:26 ` Darren New 2002-05-07 1:56 ` tmoran @ 2002-05-07 17:00 ` Wes Groleau 1 sibling, 0 replies; 88+ messages in thread From: Wes Groleau @ 2002-05-07 17:00 UTC (permalink / raw) > Somehow, tho, I thought that any software engineer would have had at > least one class about computability (or at least formal mathematics) and > would therefore have recognised the form of the statement. If you don't > recognise "a given set of machine instructions" as meaning any arbitrary > set of programs then, well, I guess you haven't studied much formally. Hey, I went to "Degrees R Us" :-) Still, there is a difference between "a set of machine instructions" and "any given set of machine instructions" > If you don't understand that sentence, then why argue with people who > explain it to you? If "recursively undecidable" doesn't mean anything to Actually, it's unclear who's arguing with who in this thread. -- Wes Groleau http://freepages.rootsweb.com/~wgroleau ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-05 23:11 ` tmoran 2002-05-06 2:13 ` Chad R. Meiners @ 2002-05-06 21:33 ` Robert Dewar 1 sibling, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-06 21:33 UTC (permalink / raw) tmoran@acm.org wrote in message news:<p_iB8.3409$9d1.36389081@newssvr21.news.prodigy.com>... > So the set of instructions emitted by Gnat when it compiles bubble sort > code may or may not constitute a general sorting algorithm, and whether > it does or not is undecidable? Of course not! That's not what I said. > I learn something new every day. Perhaps not :-) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-05 0:52 ` Robert Dewar 2002-05-05 23:11 ` tmoran @ 2002-05-06 17:26 ` Marin David Condic 2002-05-07 7:35 ` tmoran 2 siblings, 0 replies; 88+ messages in thread From: Marin David Condic @ 2002-05-06 17:26 UTC (permalink / raw) If you re-read my post, you'll notice that I did indicate you can't use it because you can't determine that it will ever finish. Its an interesting concept, but unusable as a sorting algorithm. It was a variation on an old embedded development strategy: Write a random code generator, then go into the lab and make patches until it works. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com "Robert Dewar" <dewar@gnat.com> wrote in message news:5ee5b646.0205041652.63032ba6@posting.google.com... > > You could see if it sorted some particular list, but to > determine whether a set of instructions constitutes a > general sorting algorithm is obviously recursively > undecidable. So this is not a well formed method. > ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-05 0:52 ` Robert Dewar 2002-05-05 23:11 ` tmoran 2002-05-06 17:26 ` Marin David Condic @ 2002-05-07 7:35 ` tmoran 2002-05-07 13:22 ` Marin David Condic ` (3 more replies) 2 siblings, 4 replies; 88+ messages in thread From: tmoran @ 2002-05-07 7:35 UTC (permalink / raw) > "Marin David Condic" > A better (slower) algorithm would be > to > generate a random set of machine > > instructions, execute them, see if it sorted the list > > You could see if it sorted some particular list, but to > determine whether a set of instructions constitutes a > general sorting algorithm is obviously recursively > undecidable. So this is not a well formed method. I tried an experiment*: the data is three letters chosen from 'a' .. 'c', the instructions are for a machine with instructions: compare and skip if greater, swap, jump, and stop. Generating random 16 line programs, and random data strings, and aborting any program still running after 50 instruction cycles, there were 125801 successes in 874199 tries. Testing each of the successful programs against all possible combinations of three letters from 'a' .. 'c', 9 of the programs successfully sorted all combinations, ie, were general routines capable of sorting any input data in their universe. So "recursively undecidable" is a fancy way of saying it may get stuck in an infinite loop, and, assuming he didn't mean to allow that, mcondic's algorithm is perfectly good as a (slow) sorting algorithm. * Program available on request. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 7:35 ` tmoran @ 2002-05-07 13:22 ` Marin David Condic 2002-05-08 5:23 ` tmoran 2002-05-07 15:34 ` Darren New ` (2 subsequent siblings) 3 siblings, 1 reply; 88+ messages in thread From: Marin David Condic @ 2002-05-07 13:22 UTC (permalink / raw) That's kind of where I was going. Assume you have a data set on a disk. Assume you have a processor capable of accessing that disk and that it has an instruction set represented by 32 bit numbers with some fixed quantity of memory. Fill that memory with random 32 bit numbers. Set the processor to start running at instruction 0. Did the data set on disk get sorted? No? Go back to filling memory again. (Or you could do it with a list in memory, or whatever preconditions you want to establish...) The problem, quite obviously, is that you can't determine in advance that whatever set of instructions you generated doesn't contain an infinite loop. So did the program get stuck in an infinite loop or is it just taking a *really* long time to sort the data? Given that you can't examine the random set of instructions and determine with certainty that any given combination contains an infinite loop & reject that pattern, you can't use it as a slow sort algorithm - assuming that one of the rules of slow sorting is that you guarantee the algorithm will eventually result in a sorted list of data. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com <tmoran@acm.org> wrote in message news:PsLB8.6706$cT1.98522399@newssvr21.news.prodigy.com... > So "recursively undecidable" is a fancy way of saying it may get stuck > in an infinite loop, and, assuming he didn't mean to allow that, mcondic's > algorithm is perfectly good as a (slow) sorting algorithm. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 13:22 ` Marin David Condic @ 2002-05-08 5:23 ` tmoran 2002-05-08 14:10 ` Marin David Condic 2002-05-08 16:20 ` Darren New 0 siblings, 2 replies; 88+ messages in thread From: tmoran @ 2002-05-08 5:23 UTC (permalink / raw) > start running at instruction 0. Did the data set on disk get sorted? No? Go > back to filling memory again. >... >So did the program get stuck in an infinite loop or is it just taking a >*really* long time to sort the data? As Dewar points out, you just keep snapshots of all the states the program has gone through and check for "Hey! We've been here before!". Your RAM + disk have a finite number of bits N so there are at most 2**N possible states it can wander among. If the instruction execution time is t, it can't run more than t*2**N without repeating itself. Or you can calculate how long T some standard sort algorithm would take, maximum, then abort if your randomly generated program is still running at T+1 sec. If your random program generator will create all possible configurations of RAM, then one of those is going to be identical to the standard sort algorithm and eventually you are going to come across it, guaranteed. If there are N bits in RAM, this is guaranteed to take no more than (T+1)*2**N. And you may get lucky and find a better random program sooner. Slow, yes, but not interminable. ;) > assuming that one of the rules of slow sorting is that you > guarantee the algorithm will eventually result in a sorted list of data. If no individual random program is allowed to run forever, and your random generator generates all possible programs in your finite machine, then loop generate random program; run it till done or it's in a loop or it's been running T seconds; exit when sorted; end loop; is indeed guaranteed to sort your data in a finite, albeit long, time. You can do a similar thing to generate a general sort program. loop generate random program; appears_successful := true; for all possible sets of data on your disk loop run it till done or it's in a loop or it's been running T seconds; if not data_is_sorted then appears_successful := false; exit; end if; end loop; exit when appears_successful; end loop; This too must terminate in a finite time, giving you a general sort program that will work on any set of data on your disk. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-08 5:23 ` tmoran @ 2002-05-08 14:10 ` Marin David Condic 2002-05-09 16:20 ` Darren New 2002-05-09 19:04 ` tmoran 2002-05-08 16:20 ` Darren New 1 sibling, 2 replies; 88+ messages in thread From: Marin David Condic @ 2002-05-08 14:10 UTC (permalink / raw) <tmoran@acm.org> wrote in message news:qD2C8.41$k97.25193567@newssvr13.news.prodigy.com... > As Dewar points out, you just keep snapshots of all the states the > program has gone through and check for "Hey! We've been here before!". > Your RAM + disk have a finite number of bits N so there are at most 2**N > possible states it can wander among. If the instruction execution time is > t, it can't run more than t*2**N without repeating itself. I *think* I follow - but that seems to disallow any sort of looping. (Or do I misunderstand?) Isn't it possible for a program to be in a state it has been in before (iterating through the data on disk again...) and not be caught in an infininte loop? Or because you're including a check of the state of the data as well, then it can't be in the same state plus the identical state of the data without being caught in a loop? (So if you had 1k of program+data+processor_state, you'd save every bit, execute one clock cycle, compare the 1k against every previous 1k and if it matches, its stuck and throw it out? Sounds deliciously slow! :-) Or you can > calculate how long T some standard sort algorithm would take, maximum, > then abort if your randomly generated program is still running at T+1 sec. But that's just looking for the occurrence of a specific algorithm, isn't it? Say I calculate the time needed for the Slow Sort algorithm (permutations) to get through some data and use this as the worst case. I'd reject every valid random algorithm that was T>Slow Sort. I'm sure I can come up with valid code that sorts at a time greater than that of the Slow Sort (Slow Sort plus delay (1.0), if nothing else.) So really, you're saying "I want to see how long it takes to randomly generate at least the Slow Sort algorithm." I can see that this works, but it seems sub-optimal. :-) It might make a great article & example of tasking (One task sets the other task to its sorting job & monitors the time, shooting it in the head & restarting it as needed...) to implement something like this. :-) MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-08 14:10 ` Marin David Condic @ 2002-05-09 16:20 ` Darren New 2002-05-09 19:04 ` tmoran 1 sibling, 0 replies; 88+ messages in thread From: Darren New @ 2002-05-09 16:20 UTC (permalink / raw) Marin David Condic wrote: > I *think* I follow - but that seems to disallow any sort of looping. (Or do > I misunderstand?) You misunderstand. > Isn't it possible for a program to be in a state it has > been in before (iterating through the data on disk again...) and not be > caught in an infininte loop? No. Perhaps the program counter will have a value it had before, but if every variable in the program, all the values in the registers, the data on the disk, etc, are the same, it's going to do the same thing it did last time (assuming it's deterministic, of course). > Or because you're including a check of the > state of the data as well, then it can't be in the same state plus the > identical state of the data without being caught in a loop? (So if you had > 1k of program+data+processor_state, you'd save every bit, execute one clock > cycle, compare the 1k against every previous 1k and if it matches, its stuck > and throw it out? Sounds deliciously slow! :-) Exactly. > But that's just looking for the occurrence of a specific algorithm, isn't > it? Right. Rather than a "general sort algorithm". Actually, it's interesting, because a "sorting algorithm" doesn't sort items. It orders them. When I sort my socks, I don't put them in a row, darkest to lightest. I group them by the sort of socks they are. :-) I think the unusual meaning of the word came about because a card sorter (which really did just sort the cards without ordering them) was used to order the cards, basically via repeated sorting a la radix sort. Just an interesting aside... -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-08 14:10 ` Marin David Condic 2002-05-09 16:20 ` Darren New @ 2002-05-09 19:04 ` tmoran 1 sibling, 0 replies; 88+ messages in thread From: tmoran @ 2002-05-09 19:04 UTC (permalink / raw) > > calculate how long T some standard sort algorithm would take, maximum, > > then abort if your randomly generated program is still running at T+1 sec. > > But that's just looking for the occurrence of a specific algorithm, isn't > it? Say I calculate the time needed for the Slow Sort algorithm > (permutations) to get through some data and use this as the worst case. I'd > reject every valid random algorithm that was T>Slow Sort. I'm sure I can > come up with valid code that sorts at a time greater than that of the Slow You could of course change the time requirement from T+1 second to T+one year, and that would probably uncover most sorts of interest. But you could never be sure that way that if you had just let it run a little bit longer it wouldn't have come up with a different, better algorithm. It's interesting that random generation isn't needed here, sequential Big_Number's would work just fine. Randomness buys you that the probability you have tried a point in search space arbitrarily close to any given point, gets larger, while with sequential test points it's guaranteed to take a very long time before you get anywhere near Big_Number'last. But here closeness doesn't count. You could be one bit away from a wonderful sort algorithm and, since it doesn't work, that's no better than having many bits wrong. But if, instead of a totally random new program each time, you try tweaks to the best you've seen so far, then being close does count, and randomness does help. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-08 5:23 ` tmoran 2002-05-08 14:10 ` Marin David Condic @ 2002-05-08 16:20 ` Darren New 2002-05-08 17:31 ` tmoran 2002-05-08 17:39 ` Chad R. Meiners 1 sibling, 2 replies; 88+ messages in thread From: Darren New @ 2002-05-08 16:20 UTC (permalink / raw) tmoran@acm.org wrote: > If your random program generator will create all possible configurations > of RAM, then one of those is going to be identical to the standard sort > algorithm and eventually you are going to come across it, guaranteed. If [...] I think you're making three of the usual mistakes: 1) A random program generator will not necessarily create all possible configurations of RAM unless you run it an unbounded number of times. 2) In trying to keep track of how many times you've done something, you wind up using memory that you might not have. For example, you can't take a machine with N bits and keep track of whether it has gone through every possible combination of those N bits. If it might run as long as 2**N steps, you need N bits of memory just to hold the counter telling you how many steps it has run. 3) Finite computers are uninteresting to theoreticians. :-) For exactly the reasons you're talking about, having an infinite (for some sufficiently large value of infinite) machine watch a finite machine is generally not worth studying. So a sort algorithm that only worked on lists up to a particular size is basically uninteresting, and doesn't really count as a "general sort". (These are "usual" in the sense that they seem common amongst people who haven't studied the topic a lot, worked out proofs, etc, and hence learned intuitively why certain things work and don't work. It's "usual" in the same way that people saying "language A and B are both turing complete" and thinking that says something about the power or usability of language A or language B in some useful sense.) -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-08 16:20 ` Darren New @ 2002-05-08 17:31 ` tmoran 2002-05-08 17:39 ` Chad R. Meiners 1 sibling, 0 replies; 88+ messages in thread From: tmoran @ 2002-05-08 17:31 UTC (permalink / raw) > > If your random program generator will create all possible configurations > 1) A random program generator will not necessarily create all possible > configurations of RAM unless you run it an unbounded number of times. "If X then Y" is not disproved by "not X". And you are thinking of a mathematical random generator. Randomness is not important for the original argument - completeness is, as you note. Try Seed : Big_Number_Type := 0; function Random return Big_Number_Type is begin Seed := Seed+1; return Seed-1; end Random; It may not be statistically random, but it surely returns every possible value of Big_Number_Type. > 2) In trying to keep track of how many times you've done something, you > wind up using memory that you might not have. For example, you can't Clearly you can't have the machine watch itself. I'm sorry if that wasn't clear. But a finite machine can be watched by another (larger) finite machine. > 3) Finite computers are uninteresting to theoreticians. :-) And infinite computers are of only modest interest to [software] engineers. Like proving there is no largest prime. Interesting, educational, encouraging (or discouraging), but not a reason to stop trying to make a better primality testing program. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-08 16:20 ` Darren New 2002-05-08 17:31 ` tmoran @ 2002-05-08 17:39 ` Chad R. Meiners 1 sibling, 0 replies; 88+ messages in thread From: Chad R. Meiners @ 2002-05-08 17:39 UTC (permalink / raw) "Darren New" <dnew@san.rr.com> wrote in message news:3CD9505F.344C13EA@san.rr.com... > tmoran@acm.org wrote: > 3) Finite computers are uninteresting to theoreticians. :-) Wow, that's news to me! :-) There are models of space and time bound Turing Machines so I would not say that such things are uninteresting. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 7:35 ` tmoran 2002-05-07 13:22 ` Marin David Condic @ 2002-05-07 15:34 ` Darren New 2002-05-07 17:44 ` Chad R. Meiners 2002-05-08 2:17 ` Generation of permutations Robert Dewar 3 siblings, 0 replies; 88+ messages in thread From: Darren New @ 2002-05-07 15:34 UTC (permalink / raw) tmoran@acm.org wrote: > Testing each of the successful programs against all possible combinations > of three letters from 'a' .. 'c', 9 of the programs successfully sorted > all combinations, ie, were general routines capable of sorting any > input data in their universe. I've seen this done to come up with the most efficient/shortest FORTRAN library routines. Basically, the program iterated through all possible machine code sets, starting with the shortest, until it found an instruction sequence that did the right thing. The researchers found (for example) a 2-instruction sequence that gives you the SIGN function (a<0 -> -1, a=0 -> 0, a>0 -> +1) that was totally unintuitive. (It involved, IIRC, a shift and a subtract or some such.) It was written up either in SIGPLAN or CACM about 10 years ago or so, IIRC. An interesting article. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 7:35 ` tmoran 2002-05-07 13:22 ` Marin David Condic 2002-05-07 15:34 ` Darren New @ 2002-05-07 17:44 ` Chad R. Meiners 2002-05-07 19:58 ` tmoran 2002-05-08 2:17 ` Generation of permutations Robert Dewar 3 siblings, 1 reply; 88+ messages in thread From: Chad R. Meiners @ 2002-05-07 17:44 UTC (permalink / raw) <tmoran@acm.org> wrote in message news:PsLB8.6706$cT1.98522399@newssvr21.news.prodigy.com... > So "recursively undecidable" is a fancy way of saying it may get stuck > in an infinite loop, It is more significant than that. I suggest that instead of shruging off your lack of knowledge in this important topic, you should acquire a book on the subject and read through some of it. I suggest "Introduction to the Theory of Computation" by Michael Sipser. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 17:44 ` Chad R. Meiners @ 2002-05-07 19:58 ` tmoran 2002-05-07 21:05 ` Turing-undecidable languages (OT) Chad R. Meiners 0 siblings, 1 reply; 88+ messages in thread From: tmoran @ 2002-05-07 19:58 UTC (permalink / raw) > > So "recursively undecidable" is a fancy way of saying it may get stuck > > in an infinite loop, > > It is more significant than that. If someone says "I'll write a program to do such and such", how should he act differently if told: a) that's recursively undecidable or b) your program may get stuck in an infinite loop ^ permalink raw reply [flat|nested] 88+ messages in thread
* Turing-undecidable languages (OT) 2002-05-07 19:58 ` tmoran @ 2002-05-07 21:05 ` Chad R. Meiners 2002-05-08 8:24 ` Danx 2002-05-08 9:16 ` Dmitry A. Kazakov 0 siblings, 2 replies; 88+ messages in thread From: Chad R. Meiners @ 2002-05-07 21:05 UTC (permalink / raw) <tmoran@acm.org> wrote in message news:7mWB8.6827$0z6.115522658@newssvr21.news.prodigy.com... > If someone says "I'll write a program to do such and such", how should > he act differently if told: > a) that's recursively undecidable > or > b) your program may get stuck in an infinite loop This is an excellent question. First, let's rephrase your question to: If some says, "I'll am going to write a program Y that solves problem X", how should he act if told a) X is not recursive. (This is the same as Robert's recursively undecidable) b) Program Y may get stuck in an infinite loop. In case a, Y cannot exist. Case b depends solely on what you meant by "may get stuck in an infinite loop". In fact the pragmatics of b can either be X is recursive or X is not recursive. So the only thing the programmer can do if told b is ask for clarification. -CRM ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Turing-undecidable languages (OT) 2002-05-07 21:05 ` Turing-undecidable languages (OT) Chad R. Meiners @ 2002-05-08 8:24 ` Danx 2002-05-08 17:16 ` Chad R. Meiners 2002-05-10 2:37 ` Robert Dewar 2002-05-08 9:16 ` Dmitry A. Kazakov 1 sibling, 2 replies; 88+ messages in thread From: Danx @ 2002-05-08 8:24 UTC (permalink / raw) "Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<ab9fmh$2qh1$1@msunews.cl.msu.edu>... > This is an excellent question. First, let's rephrase your question to: > > If some says, "I'll am going to write a program Y that solves problem X", > how should he act if told > > a) X is not recursive. (This is the same as Robert's recursively > undecidable) > b) Program Y may get stuck in an infinite loop. > > In case a, Y cannot exist. Does that mean that if any problem cannot be expressed recursively, then no program can be coded to solve it? In other words, any problem that can be solved without recursion, can also be expressed using recursion and any problem that cannot be solved by recursion cannot be solved by a computer? Chris ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Turing-undecidable languages (OT) 2002-05-08 8:24 ` Danx @ 2002-05-08 17:16 ` Chad R. Meiners 2002-05-10 2:37 ` Robert Dewar 1 sibling, 0 replies; 88+ messages in thread From: Chad R. Meiners @ 2002-05-08 17:16 UTC (permalink / raw) "Danx" <chris.danx@ntlworld.com> wrote in message news:da2da981.0205080024.6576be16@posting.google.com... > "Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<ab9fmh$2qh1$1@msunews.cl.msu.edu>... > Does that mean that if any problem cannot be expressed recursively, > then no program can be coded to solve it? In other words, any problem > that can be solved without recursion, can also be expressed using > recursion and any problem that cannot be solved by recursion cannot be > solved by a computer? Recursive refers to a set of languages. When we say x is recursive, we mean x in is the set of recursive languages. This is why I prefer the term Turing-decidable. As to the above question, we must be careful with phrases "cannot be solved by recursion" because they are vague. Context free grammars are recursively defined yet they are less powerful then Turing Machines, but I guess the best general answer is that Turing Machines can simulate arbitrary recursion and nonrecursive algorithms can be thought as a subset of recursive algorithms. So given that explanation, you can solve X with recursion if and only if you can solve X with a Turing Machine. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Turing-undecidable languages (OT) 2002-05-08 8:24 ` Danx 2002-05-08 17:16 ` Chad R. Meiners @ 2002-05-10 2:37 ` Robert Dewar 1 sibling, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-10 2:37 UTC (permalink / raw) chris.danx@ntlworld.com (Danx) wrote in message news:<da2da981.0205080024.6576be16@posting.google.com>... > "Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<ab9fmh$2qh1$1@msunews.cl.msu.edu>... > > Does that mean that if any problem cannot be expressed > recursively, then no program can be coded to solve it? > In other words, any problem that can be solved without > recursion, can also be expressed using recursion and any > problem that cannot be solved by recursion cannot be > solved by a computer? Oh dear! Another terminology confusion. Recursively decidable means that an algorithm can be written in a normal recursive formalism (e.g. lambda calculus). It has little to do with the use of "recursion" in a procedural language. Think of it as just meaning (programmable in a normal programming language) and you will not be far off. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Turing-undecidable languages (OT) 2002-05-07 21:05 ` Turing-undecidable languages (OT) Chad R. Meiners 2002-05-08 8:24 ` Danx @ 2002-05-08 9:16 ` Dmitry A. Kazakov 2002-05-08 17:18 ` Chad R. Meiners 1 sibling, 1 reply; 88+ messages in thread From: Dmitry A. Kazakov @ 2002-05-08 9:16 UTC (permalink / raw) On Tue, 7 May 2002 17:05:50 -0400, "Chad R. Meiners" <crmeiners@hotmail.com> wrote: ><tmoran@acm.org> wrote in message >news:7mWB8.6827$0z6.115522658@newssvr21.news.prodigy.com... >> If someone says "I'll write a program to do such and such", how should >> he act differently if told: >> a) that's recursively undecidable >> or >> b) your program may get stuck in an infinite loop > >This is an excellent question. First, let's rephrase your question to: > >If some says, "I'll am going to write a program Y that solves problem X", >how should he act if told > >a) X is not recursive. (This is the same as Robert's recursively >undecidable) >b) Program Y may get stuck in an infinite loop. > >In case a, Y cannot exist. Surely but only if Y would do no I/O and thus have no connection to some external sources of knowledge. Consider a program that insolently asks the operator, "hey, maybe you know the answer"? (:-)) --- Regards, Dmitry Kazakov www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Turing-undecidable languages (OT) 2002-05-08 9:16 ` Dmitry A. Kazakov @ 2002-05-08 17:18 ` Chad R. Meiners 2002-05-09 20:56 ` Dmitry A.Kazakov 0 siblings, 1 reply; 88+ messages in thread From: Chad R. Meiners @ 2002-05-08 17:18 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:ionhduku9trnt8pdm11ovutkp7g8jb0bjd@4ax.com... > Surely but only if Y would do no I/O and thus have no connection to > some external sources of knowledge. Consider a program that insolently > asks the operator, "hey, maybe you know the answer"? (:-)) How would that be different from using an oracle? It is clear that Turing Machines will oracles can solve the halting problem. The problem of course is building the oracle. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Turing-undecidable languages (OT) 2002-05-08 17:18 ` Chad R. Meiners @ 2002-05-09 20:56 ` Dmitry A.Kazakov 2002-05-09 16:18 ` Chad R. Meiners 0 siblings, 1 reply; 88+ messages in thread From: Dmitry A.Kazakov @ 2002-05-09 20:56 UTC (permalink / raw) Chad R. Meiners wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message > news:ionhduku9trnt8pdm11ovutkp7g8jb0bjd@4ax.com... >> Surely but only if Y would do no I/O and thus have no connection to >> some external sources of knowledge. Consider a program that insolently >> asks the operator, "hey, maybe you know the answer"? (:-)) > > How would that be different from using an oracle? It is not different and we are permanently doing so by asking small oracles like hardware random generators, timers etc in our programs. > It is clear that Turing > Machines will oracles can solve the halting problem. The problem of > course is building the oracle. Yes. The point is that often the term "program" is ill-defined leaving enough room for discussions which otherwise would have no place. If I correctly understood it, Tom considers a problem regading programs of fixed size, while opponents attack him with the results valid for infinite cases. -- Regards, Dmitry Kazakov www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Turing-undecidable languages (OT) 2002-05-09 20:56 ` Dmitry A.Kazakov @ 2002-05-09 16:18 ` Chad R. Meiners 2002-05-10 2:52 ` Robert Dewar 0 siblings, 1 reply; 88+ messages in thread From: Chad R. Meiners @ 2002-05-09 16:18 UTC (permalink / raw) "Dmitry A.Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:abddca$h96t0$1@ID-77047.news.dfncis.de... > If I > correctly understood it, Tom considers a problem regading programs of fixed > size, while opponents attack him with the results valid for infinite cases. Where do you see people attacking Tom in this discusion of TMs? This whole discusion started when Tom replied to Robert with the following statement: > So the set of instructions emitted by Gnat when it compiles bubble sort > code may or may not constitute a general sorting algorithm, and whether > it does or not is undecidable? I learn something new every day. I tried to clarify Robert's statement and answer some other questions as they poped up. But as far as attacking Tom's idea of randoming generating sorting algoritms with predefined time and space bounds, I would do no such thing because placing bounds on algorithms is one way to change the halting problem to make it decidable. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Turing-undecidable languages (OT) 2002-05-09 16:18 ` Chad R. Meiners @ 2002-05-10 2:52 ` Robert Dewar 0 siblings, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-10 2:52 UTC (permalink / raw) "Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<abe7ir$2ktu$1@msunews.cl.msu.edu>... > I tried to clarify Robert's statement and answer some other questions as > they poped up. But as far as attacking Tom's idea of randoming generating > sorting algoritms with predefined time and space bounds, I would do no such > thing because placing bounds on algorithms is one way to change the halting > problem to make it decidable. True, but a problem that is theoretically recursively undecidable over infinite inputs is typically practically unsolvable if the only bound is available memory, available disk space etc. So appealing to this is not particularly interesting in practice. Yes, of course we know that from a theoretical point of view, any bounding of a problem changes things completely. For example, there are many problems that are NP complete, but as soon as you limit the size, they are theoretically trivial. For example, consider the problem of coloring an N node graph on a RAM machine with unit time access to memory. If you limit N to googol**googol, then there is a trivial algorithm that yields whether the graph can be colored with M colors (again limit M), by simple table lookup in unit time. But that is not particularly interesting and in practice, coloring is still hard :-) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-07 7:35 ` tmoran ` (2 preceding siblings ...) 2002-05-07 17:44 ` Chad R. Meiners @ 2002-05-08 2:17 ` Robert Dewar 3 siblings, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-08 2:17 UTC (permalink / raw) tmoran@acm.org wrote in message news:<PsLB8.6706$cT1.98522399@newssvr21.news.prodigy.com>.. > So "recursively undecidable" is a fancy way of saying > it may get stuck in an infinite loop. Nope! That's quite wrong. In fact it is quite easy to detect if you are in an infinite loop. You use the same technique as you use in a chess match to limit repeated positions, you just remember all previous states, and if a state is repeated, you know you are in a non-halting situation. So if this was all that halting was about, there would not be a problem. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-02 16:16 ` Mark Biggar 2002-05-03 13:04 ` Marin David Condic @ 2002-05-03 13:13 ` Ted Dennison 2002-05-03 13:24 ` Lutz Donnerhacke 1 sibling, 1 reply; 88+ messages in thread From: Ted Dennison @ 2002-05-03 13:13 UTC (permalink / raw) Mark Biggar <mark.a.biggar@attbi.com> wrote in message news:<3CD1664A.804F56BC@attbi.com>... > There are worse sorts then Bogosort. For example there is 52-pickup > sort: repeatedly randomize the list until you notice that it > is sorted. No, that's just a form of bogosort where the permutations are picked randomly. In the average case, it should have the exact same time behavour. In fact, someone suggesting just that was the inspiration I needed to create my "Permutesort" back in the mid-80's. -- T.E.D. Home - mailto:dennison@telepath.com (Yahoo: Ted_Dennison) Homepage - http://www.telepath.com/dennison/Ted/TED.html ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-03 13:13 ` Ted Dennison @ 2002-05-03 13:24 ` Lutz Donnerhacke 0 siblings, 0 replies; 88+ messages in thread From: Lutz Donnerhacke @ 2002-05-03 13:24 UTC (permalink / raw) * Ted Dennison wrote: >Mark Biggar <mark.a.biggar@attbi.com> wrote in message news:<3CD1664A.804F56BC@attbi.com>... >> There are worse sorts then Bogosort. For example there is 52-pickup >> sort: repeatedly randomize the list until you notice that it >> is sorted. > >No, that's just a form of bogosort where the permutations are picked >randomly. In the average case, it should have the exact same time >behavour. Random permutations until sorted is not as bad as expected for a good bogo. The worst case is still "one step". There is a university dealing with such problems more deeply: http://www.ru-eschweilerhof.de/cs/fb17/ (German website) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 13:52 ` Ted Dennison 2002-04-30 14:20 ` Marin David Condic @ 2002-04-30 15:06 ` Hyman Rosen 2002-05-01 8:40 ` Adrian Hoe 2002-05-11 1:52 ` Steven Deller 2002-05-02 16:24 ` Mark Biggar 2 siblings, 2 replies; 88+ messages in thread From: Hyman Rosen @ 2002-04-30 15:06 UTC (permalink / raw) Ted Dennison wrote: > Reinert Korsnes <reinert.korsnes@chello.no> wrote in message news:<aajce7$7jb$1@snipp.uninett.no>... > >>Are there any good (Ada95) packages for generation of permutations >>(of elements in array) ? > > Sadly, that doesn't come up much...outside of homework assignments. ;-) > Are you writing a bogosort? Whether or not it comes up much, in fact the algorithms next_permutation and prev_permutation are part of the C++ standard library. You can find them online in <http://www.sgi.com/tech/stl/stl_algo.h>. It should not be too difficult for the OP to translate them to Ada. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 15:06 ` Hyman Rosen @ 2002-05-01 8:40 ` Adrian Hoe 2002-05-01 19:53 ` Hyman Rosen 2002-05-11 1:52 ` Steven Deller 1 sibling, 1 reply; 88+ messages in thread From: Adrian Hoe @ 2002-05-01 8:40 UTC (permalink / raw) Hyman Rosen <hyrosen@mail.com> wrote in message news:<3CCEB2E0.7050701@mail.com>... > Ted Dennison wrote: > Whether or not it comes up much, in fact the algorithms > next_permutation and prev_permutation are part of the C++ > standard library. You can find them online in > <http://www.sgi.com/tech/stl/stl_algo.h>. Oouch! A good example of low readability. :) -- Adrian Hoe -- http://adrianhoe.com ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-01 8:40 ` Adrian Hoe @ 2002-05-01 19:53 ` Hyman Rosen 0 siblings, 0 replies; 88+ messages in thread From: Hyman Rosen @ 2002-05-01 19:53 UTC (permalink / raw) Adrian Hoe wrote: > Oouch! A good example of low readability. :) Becuase of macros and C++ file inclusion model for referencing modules, implementations of the standard library have to use funny identifiers, starting either with __ or _[A-Z] to stay out of the way of user names. But yes, it's no gem. ^ permalink raw reply [flat|nested] 88+ messages in thread
* RE: Generation of permutations 2002-04-30 15:06 ` Hyman Rosen 2002-05-01 8:40 ` Adrian Hoe @ 2002-05-11 1:52 ` Steven Deller 1 sibling, 0 replies; 88+ messages in thread From: Steven Deller @ 2002-05-11 1:52 UTC (permalink / raw) [-- Attachment #1: Type: text/plain, Size: 1419 bytes --] Write one way back when starting Ada 83 (1984). Based on Djkstra's algoritm in A Discipline of Programming. Is this what you want. (Sorry for the long delay -- I only get to read CLA once every few weeks when flying on a plane). It only does a next perumutation, but a "previous" permutation is pretty simple to devise. Use WP's to even prove it :-). Regards, Steve Deller > -----Original Message----- > From: comp.lang.ada-admin@ada.eu.org > [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Hyman Rosen > Sent: Tuesday, April 30, 2002 11:06 AM > To: comp.lang.ada@ada.eu.org > Subject: Re: Generation of permutations > > > Ted Dennison wrote: > > Reinert Korsnes <reinert.korsnes@chello.no> wrote in message > > news:<aajce7$7jb$1@snipp.uninett.no>... > > > >>Are there any good (Ada95) packages for generation of permutations > >>(of elements in array) ? > > > > Sadly, that doesn't come up much...outside of homework assignments. > > ;-) Are you writing a bogosort? > > Whether or not it comes up much, in fact the algorithms > next_permutation and prev_permutation are part of the C++ > standard library. You can find them online in <http://www.sgi.com/tech/stl/stl_algo.h>. It should not be too difficult for the OP to translate them to Ada. _______________________________________________ comp.lang.ada mailing list comp.lang.ada@ada.eu.org http://ada.eu.org/mailman/listinfo/comp.lang.ada [-- Attachment #2: permuting.a --] [-- Type: application/octet-stream, Size: 1094 bytes --] ------------------------------------------------------------------------------ -- package PERMUTING -- Provides a Permute generic package. The generic parameters are an element -- of any type, an index of discrete type, and an ordering function. The -- package defines a list data type and procedure. The procedure takes a -- single argument of list type, and rearranges it to the next lexical -- permutation. The exception "no_more_permutations" is raised when the -- input list is lexically the last permutation. -- The algorithm is derived from that presented in Dijkstra's "A Discipline of -- Programming". ------------------------------------------------------------------------------ package Permuting is generic type Element is private; type Index is (<>); with function "<=" ( left, right: Element ) return Boolean is <>; package Permute is type List is array (Index range <>) of Element; procedure Permute ( L: in out List ); No_more_permutations : exception ; end Permute ; pragma Share_Body ( Permute , False ) ; end Permuting ; [-- Attachment #3: permutingB.a --] [-- Type: application/octet-stream, Size: 2067 bytes --] ------------------------------------------------------------------------------ -- package body PERMUTING ------------------------------------------------------------------------------ package body Permuting is package body Permute is procedure Exchange ( I, J: in out Element ) is Temp: Element; begin Temp := I; I := J; J := Temp; end Exchange; pragma Inline ( Exchange ); procedure Permute ( L: in out List ) is I, J : Index ; begin -- procedure Permute -- Find the list tail, the largest end sequence that is all in order. -- Find I, the last list position (largest i) where L(I) < L(I+1) -- and the list tail is then all elements from L(I+1) on. I := Index'pred( L'last ) ; while ( I >= L'first and then L(Index'succ(I)) <= L(I) ) loop I := Index'pred(I) ; end loop ; if -- no such I exists (complete list is monotonically decreasing) ( I < L'first ) then raise No_more_permutations ; -- because list is already lexically last end if ; -- Find J in the tail, such that L(J) is the smallest value -- for which L(J) > L(I). -- Note that L(I+1) > L(I) so at least one tail value is -- larger than L(I), though there are usually more. -- Note also that the tail is in decreasing order, so we need only -- search from the end backwards until we find a value that is larger. J := L'last ; while ( L(J) <= L(I) ) loop J := Index'pred(J) ; end loop ; Exchange( L(I), L(j) ) ; -- Put values in the tail into monotonically increasing order. -- Note that the tail is monotonically decreasing, so we need only -- reverse the order of values in the tail. I := Index'succ(I) ; J := L'last ; while ( I < J ) loop Exchange( L(I), L(J) ) ; I := Index'succ(I) ; J := Index'pred(J) ; end loop ; -- List now contains the next lexical permutation of its values. end Permute ; begin -- package Permute null ; end Permute ; begin null ; end Permuting ; ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 13:52 ` Ted Dennison 2002-04-30 14:20 ` Marin David Condic 2002-04-30 15:06 ` Hyman Rosen @ 2002-05-02 16:24 ` Mark Biggar 2 siblings, 0 replies; 88+ messages in thread From: Mark Biggar @ 2002-05-02 16:24 UTC (permalink / raw) Ted Dennison wrote: > > Reinert Korsnes <reinert.korsnes@chello.no> wrote in message news:<aajce7$7jb$1@snipp.uninett.no>... > > Are there any good (Ada95) packages for generation of permutations > > (of elements in array) ? > > Sadly, that doesn't come up much...outside of homework assignments. ;-) > > Are you writing a bogosort? If you want to roll your own code then you should look at the latest fascicle preprint from Knuth Vol. 4 "Generating Permutations" http:sunburn.stanford.edu/~knuth/fasc2b.ps.gz -- Mark Biggar mark.a.biggar@attbi.com ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-29 11:54 Generation of permutations Reinert Korsnes 2002-04-30 13:52 ` Ted Dennison @ 2002-04-30 17:12 ` Wes Groleau 2002-04-30 22:57 ` Robert Dewar 1 sibling, 1 reply; 88+ messages in thread From: Wes Groleau @ 2002-04-30 17:12 UTC (permalink / raw) > Are there any good (Ada95) packages for generation of permutations > (of elements in array) ? I can't get through to a search engine, so I can't tell you where to find the attached code now. I got it from SIMTEL-20. I have made some modifications to it. I don't remember whether any of my improvements included Ada-95 features. ------------------------------------------------------------------------------ -- Date/Author 15 Apr 1985 / Doug Bryan (Stanford University) -- -- Copyright (C) 1997 Doug Bryan, Wes Groleau, and -- the Free Software Foundation -- -- Tedious but important Legal Stuff: -- -- The original author claimed no copyright. In order to protect -- what seemed to be his intent, I am assigning copyright to the -- Free Software Foundation with the condtions below. I reserve the -- right to revoke this assignment if and when requested by the -- original author. -- -- package Permutations is free software; you can redistribute it -- and/or modify it under terms of the GNU General Public License as -- published by the Free Software Foundation; either version 2, or -- at your option) any later version. package Permutations is -- distributed in the hope that it will be useful, but WITHOUT ANY -- WARRANTY; without even the implied warranty of MERCHANTABILITY or -- FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public -- License for more details. You should have received a copy of the -- GNU General Public License distributed with GNARL; see file -- COPYING. If not, write to the Free Software Foundation, 59 Temple -- Place - Suite 330, Boston, MA 02111-1307, USA. -- -- As a special exception, if other files instantiate generics from -- this package, and/or you link with other files to produce an -- executable, this package does not by itself cause the resulting -- executable to be covered by the GNU General Public License. This -- exception does not however invalidate any other reasons why the -- executable file might be covered by the GNU Public License. ------------------------------------------------------------------------------ -- Basic algorithm from: -- "Programming in Modula-2" by Niklaus Wirth -- Chapter 14: Recursion Now just in case this is a homework assignment, I have intentionally made the code uncompilable in a way that should be quite easy for an Ada programmer to figure out and undo. with Exchange; package body Permutations is procedure Swap is new Exchange ( Item_Type ); -- The procedure permutes the elements in the array Of_Items. -- Actually it permutes their indices and re-arranges the items -- within the list. It's irrelevant whether any or all of the items -- in the list are equal (the same). procedure Iterate_Through_All_Permutations (Of_Items : List_Type) is Buffer : List_Type (Of_Items'Range) := Of_Items; procedure Permute (K : Index_Type) is -- Swap successive elements of Buffer (Buffer'First .. K) -- and permute slices. This algorithm works backwords -- through the array (in reverse Buffer'range). begin if K = Buffer'First then -- At the begining of the array. Done. Process result. Process_One_Item (A_Permutation => Buffer); else --Decrement K and permute lower slice. Permute (Index_Type'Pred (K)); -- Traverse lower slice. for I in Buffer'First .. Index_Type'Pred (K) loop -- swap K-th and I-th elements. Swap (Buffer (I), Buffer (K)); -- Decrement K and permute lower slice. Permute (Index_Type'Pred (K)); -- swap K-th and I-th elements back (restore). Swap (Buffer (I), Buffer (K)); end loop; end if; end Permute; begin Permute (Buffer'Last); end Iterate_Through_All_Permutations; end Permutations; -- -- Date/Author 15 Apr 1985 / Doug Bryan (Stanford University) -- -- Copyright (C) 1997 Doug Bryan, Wes Groleau, and -- the Free Software Foundation generic type Item_Type is private; type Index_Type is (<>); type List_Type is array (Index_Type range <>) of Item_Type; package Permutations is -- Abstract -- -- This is a generic package which, given an array of items, forms -- all possible permutations using these items. The package does so -- by providing a generic permutation class, within which is an -- iterator. The iterator has a generic formal subprogram to which -- it passes each permutation. -- -- The package may make a nice example of the following Ada features: -- nested generics, recursion, generic formal subprograms as a method -- of implementing an iterator. -- -- Tedious but important Legal Stuff: -- -- The original author claimed no copyright. In order to protect -- what seemed to be his intent, I am assigning copyright to the -- Free Software Foundation with the conditions and exceptions -- detailed in the package body. I reserve the right to revoke this -- assignment if and when requested by the original author. generic with procedure Process_One_Item (A_Permutation : List_Type); procedure Iterate_Through_All_Permutations (Of_Items : List_Type); -- For an actual parameter Of_Items of length n, n! permutations -- will be produced. end Permutations; -------- SIMTEL20 Ada Software Repository Prologue ------------ -- -* -- Unit name : Permute_Test -- Version : 1.0 -- Author : Doug Bryan -- : Computer Systems Lab -- : Stanford University -- : Stanford, CA 94305 -- DDN Address : bryan@su-sierra -- Copyright : (c) -none- -- Date created : 15 April 1985 -- Release date : 15 April 1985 -- Last update : 15 April 1985 -- Machine/System Compiled/Run on : DG MV/10000 ADE 2.2 -- -* -- -* -- Keywords : Test example instantiation ----------------: -- -- Abstract : ----------------: This main program is simply a test and example ----------------: use of the Permutation_Class package. ----------------: -- -* ------------------ Revision history --------------------------- -- -* -- DATE VERSION AUTHOR HISTORY -- -* ------------------ Distribution and Copyright ----------------- -- -* -- This prologue must be included in all copies of this software. -- -- This software is copyright by the author. -- -- This software is released to the Ada community. -- This software is released to the Public Domain (note: -- software released to the Public Domain is not subject -- to copyright protection). -- Restrictions on use or distribution: NONE -- -* ------------------ Disclaimer --------------------------------- -- -* -- This software and its documentation are provided "AS IS" and -- without any expressed or implied warranties whatsoever. -- No warranties as to performance, merchantability, or fitness -- for a particular purpose exist. -- -- Because of the diversity of conditions and hardware under -- which this software may be used, no warranty of fitness for -- a particular purpose is offered. The user is advised to -- test the software thoroughly before relying on it. The user -- must assume the entire risk and liability of using this -- software. -- -- In no event shall any person or organization of people be -- held responsible for any direct, indirect, consequential -- or inconsequential damages or lost profits. -- -* -------------------END-PROLOGUE-------------------------------- with Text_Io, Permutations_Class; use Text_Io; procedure Permute_Test is type Integer_List is array (Positive range <>) of Integer; package I_Perms is new Permutations_Class (Item_Type => Integer, Index_Type => Positive, List_Type => Integer_List); package C_Perms is new Permutations_Class (Item_Type => Character, Index_Type => Positive, List_Type => String); procedure Print_Integer_List (A_List : Integer_List); procedure Print_String (A_String : String); procedure View_Integer_Perms is new I_Perms.Iterate_Through_Length_Factorial_Permutations (Process => Print_Integer_List); procedure View_Character_Perms is new C_Perms.Iterate_Through_Length_Factorial_Permutations (Process => Print_String); package N_Io is new Integer_Io (Natural); use N_Io; C : String (1 .. 20); I : Integer_List (1 .. 20); N : Natural; procedure Print_Integer_List (A_List : Integer_List) is begin for I in A_List'Range loop Put (Integer'Image (A_List (I))); Put (' '); end loop; New_Line; end Print_Integer_List; procedure Print_String (A_String : String) is begin Put_Line (A_String); end Print_String; begin -- test permute New_Page; New_Line (2); Put_Line ("This thing permutes sequences. "); Put ("Enter n (0 .. 20) > "); Get (N); New_Line; Put_Line ("Enter " & Natural'Image (N) & " integers."); for T in 1 .. N loop Put (" > "); Get (I (T)); end loop; New_Line; Put_Line ("The permutations of the sequence"); Put (" "); Print_Integer_List (I (1 .. N)); Put_Line (" are:"); View_Integer_Perms (I (1 .. N)); Put_Line ("------------------------------------------------"); Put ("Enter n (0 .. 20) > "); Get (N); New_Line; Put_Line ("Enter " & Natural'Image (N) & " characters."); for T in 1 .. N loop Put (" > "); Get (C (T)); New_Line; end loop; New_Line; Put_Line ("The permutations of the sequence"); Put (" "); Print_String (C (1 .. N)); Put_Line (" are:"); View_Character_Perms (C (1 .. N)); exception when others => Put_Line ("Fatal exception propagation."); end Permute_Test; pragma Main; -- Wes Groleau http://freepages.rootsweb.com/~wgroleau ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 17:12 ` Wes Groleau @ 2002-04-30 22:57 ` Robert Dewar 2002-05-01 0:54 ` tmoran 2002-05-01 14:55 ` Wes Groleau 0 siblings, 2 replies; 88+ messages in thread From: Robert Dewar @ 2002-04-30 22:57 UTC (permalink / raw) Wes Groleau <wesgroleau@despammed.com> wrote in message news:<3CCED088.61B3AAE2@despammed.com>... This seemed so seriously in error that I feel I should post a comment. > -- Tedious but important Legal Stuff: > -- > -- The original author claimed no copyright. In order to protect > -- what seemed to be his intent, I am assigning copyright to the > -- Free Software Foundation with the condtions below. I reserve the > -- right to revoke this assignment if and when requested by the > -- original author. This doesn't sound like legal stuff (tedious or otherwise) to me, it sounds like a clear copyright violation. A lot of people (the writer of the above presumably included) are under the illusion that an author must explicitly "claim" copyright by including an explicit copyright message. This is totally false under current law. All material is copyrighted unless the author explicitly disclaims copyright. Only the author of a piece of software can offer to assign the copyright to someone else, and this assignment is only valid if an appropriate instrument of assignment is signed by both parties. You can't just slap "copyright FSF" on something and think it is assigned even if you ARE the author, and if you are not the author, it is seriously wrong to pretend that you can do this assignment. By copying this software without taking the trouble to check on the status, the author of the above message is almost certainly committing a violation of the author's copyright. Wes then by posting this package has also committed a violation, and anyone copying this message will also be violating the copyright. At $50,000 each, the statutory penalty for copyright violation, it sounds like the author can get rich :-) Note that it is not a defense to claim you didn't know. If you have access, and you copy, you are guilty. This is why it is SO essential to ensure that you have proper license to things you copy. For example, the mere fact that there is a GPL notice on file you obtain from the net does not mean you have the right to copy it. You have to first ensure that the copyright holder has in fact issued this license. You first have to find out who the copyright holder is. As this example shows, that may not be easy. I take the opportunity to write this off-topic contribution to this thread because this seems an area where a lot of people have a lot of very wrong ideas. Note that I am not an attorney, so this is not legal advice, merely my best understanding as an expert in copyright law on the state of things! Robert Dewar ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 22:57 ` Robert Dewar @ 2002-05-01 0:54 ` tmoran 2002-05-01 9:42 ` Florian Weimer ` (2 more replies) 2002-05-01 14:55 ` Wes Groleau 1 sibling, 3 replies; 88+ messages in thread From: tmoran @ 2002-05-01 0:54 UTC (permalink / raw) > By copying this software without taking the trouble to check on the status, > the author of the above message is almost certainly committing a violation > of the author's copyright. Wes then by posting this package has also committed > a violation, and anyone copying this message will also be violating the > copyright. At $50,000 each, the statutory penalty for copyright violation, it > sounds like the author can get rich :-) Before Wes beats it to Rio, I'd note: "Registration with the United States Copyright Office is, however, required to bring a lawsuit to enforce your copyright." in The Software Developer's and Marketer's Legal Companion, c 1993. Also "Registered works may be eligible for statutory damages and attorney's fees in successful litigation." at http://www.copyright.gov/faq.html#q14 So there's hope that it wasn't put on Simtel 17 years ago in the hope Doug Bryan could grab some easy money. Maybe someone will e-mail all Simtel material authors suggesting they register, sue everyone who picks up the bait, and pay a finder's fee to the e-mailer, who will then get rich. ;) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-01 0:54 ` tmoran @ 2002-05-01 9:42 ` Florian Weimer 2002-05-02 12:34 ` Robert Dewar 2002-05-01 12:43 ` Robert Dewar 2002-05-01 12:46 ` Generation of permutations Robert Dewar 2 siblings, 1 reply; 88+ messages in thread From: Florian Weimer @ 2002-05-01 9:42 UTC (permalink / raw) tmoran@acm.org writes: > Before Wes beats it to Rio, I'd note: "Registration with the United > States Copyright Office is, however, required to bring a lawsuit to > enforce your copyright." in The Software Developer's and Marketer's Legal > Companion, c 1993. Law has changed, AFAIK. Back in 1986 or so, any work which didn't carry a copyright notice was even automatically in the public domain. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-01 9:42 ` Florian Weimer @ 2002-05-02 12:34 ` Robert Dewar 0 siblings, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-02 12:34 UTC (permalink / raw) Florian Weimer <fw@deneb.enyo.de> wrote in message news:<874rhs2ogu.fsf@deneb.enyo.de>... > tmoran@acm.org writes: > > > Before Wes beats it to Rio, I'd note: "Registration with the United > > States Copyright Office is, however, required to bring a lawsuit to > > enforce your copyright." in The Software Developer's and Marketer's Legal > > Companion, c 1993. > > Law has changed, AFAIK. Back in 1986 or so, any work which didn't > carry a copyright notice was even automatically in the public domain. That's true, but irrelevant to the quoted text. Indeed it is the case that works are automatically copyrighted, with or without a notice, and it is also correct that you have to register to bring a lawsuit. But the latter requirement is not a great burden (just register when you bring the suit) Robert Dewar P.S. As I mentioned before under certain circumstances, failure to register timely causes the presumption of originality to be lost. Consult your attorney for details if this is a concern to you. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-01 0:54 ` tmoran 2002-05-01 9:42 ` Florian Weimer @ 2002-05-01 12:43 ` Robert Dewar 2002-05-01 15:05 ` TO WHOM IT MAY CONCERN Wes Groleau 2002-05-01 12:46 ` Generation of permutations Robert Dewar 2 siblings, 1 reply; 88+ messages in thread From: Robert Dewar @ 2002-05-01 12:43 UTC (permalink / raw) tmoran@acm.org wrote in message news:<11Hz8.4180$PE6.2467133575@newssvr21.news.prodigy.com>... > Before Wes beats it to Rio, I'd note: "Registration with the United > States Copyright Office is, however, required to bring a lawsuit to > enforce your copyright." in The Software Developer's and Marketer's Legal > Companion, c 1993. Also "Registered works may be eligible for statutory > damages and attorney's fees in successful litigation." at > http://www.copyright.gov/faq.html#q14 So there's hope that it wasn't put > on Simtel 17 years ago in the hope Doug Bryan could grab some easy money. > Maybe someone will e-mail all Simtel material authors suggesting they > register, sue everyone who picks up the bait, and pay a finder's fee to > the e-mailer, who will then get rich. ;) Yes, of course you have to register the copyright to bring action. But you own the copyright without registration, and you just register to bring the action, happens all the time. In fact it is almost the norm to not bother to register until you need to take legal action. So the fact that something is not registered does not mean you can copy it with impunity. It is true that under some circumstances, failure to timely register can lose the presumption of originality, but that only happens in a narrow set of circumstances, and in any case only shifts the burden of proof, not the potential liability for the copyright violation. People should learn to take copyright law more seriously in this field. Now that so much stuff floats around pretty freely on the net, anyone downloading anything must put in some effort to ensure that they are not violating copyrights, or they take a risk. Yes, for personal use, a lot of people will take at face value a license agreement on a file that purports to give appropriate rights, and that's probably reasonable, but if you are doing serious work, you need to be more careful. And nothing can excuse this odd situation where party A writes some software, party B grabs it, slaps on a copyright notice and then claims to have assigned to party C without any involvement of parties A or C. By the way, a copyright notice that reads copyrighted by X and the FSF is almost certainly bogus. This is not the standard form of statement on anything to which the FSF legitimately and actually holds copyright interest. ^ permalink raw reply [flat|nested] 88+ messages in thread
* TO WHOM IT MAY CONCERN 2002-05-01 12:43 ` Robert Dewar @ 2002-05-01 15:05 ` Wes Groleau 2002-05-02 12:27 ` More on copyright, (Re: TO WHOM IT MAY CONCERN) Robert Dewar 0 siblings, 1 reply; 88+ messages in thread From: Wes Groleau @ 2002-05-01 15:05 UTC (permalink / raw) > By the way, a copyright notice that reads > > copyrighted by X and the FSF > > is almost certainly bogus. This is not the standard form of statement "Standard form" makes the lawyer's job easier when it applies. There are no rules of procedure (to my knowledge) that say the actual meaning is less important than the choice of words. TO EVERYONE WHO SAW THE OTHER MESSAGE: I hereby explicitly claim copyright on all differences between that message and the original submission to SIMTEL-20. I hereby withdraw ANY rights I've assigned to the FSF for ANY copies made anywhere, any time. I hereby give permission to anybody, anywhere & anytime to make the same changes. I hereby promise that anyone who sues me on it will, before it's over, find that their legal fees are more than my net worth, and possibly more than my anticipated future income. End of thread (I hope). -- Wes Groleau http://freepages.rootsweb.com/~wgroleau ^ permalink raw reply [flat|nested] 88+ messages in thread
* More on copyright, (Re: TO WHOM IT MAY CONCERN) 2002-05-01 15:05 ` TO WHOM IT MAY CONCERN Wes Groleau @ 2002-05-02 12:27 ` Robert Dewar 2002-05-08 13:56 ` Wes Groleau 0 siblings, 1 reply; 88+ messages in thread From: Robert Dewar @ 2002-05-02 12:27 UTC (permalink / raw) Wes Groleau <wesgroleau@despammed.com> wrote in message news:<3CD0043A.AB588053@despammed.com>... > TO EVERYONE WHO SAW THE OTHER MESSAGE: > > I hereby explicitly claim copyright on all differences > between that message and the original submission > to SIMTEL-20. I hereby withdraw ANY rights > I've assigned to the FSF for ANY copies made > anywhere, any time. I hereby give permission > to anybody, anywhere & anytime to make the same > changes. But you can't claim copyright here. You have created a deriviative work without the original authors permission. That is in itself a copyright violation. You can only create a deriviative work if you have an agreement with the original author to do so. Whether that agreement leaves you with any copyright interest is a matter to be decided by the copyright agreement. You are not in a position to give permission to others to repeat the same violation of copyright. Yes, of course in this case it is *probably* OK, and yes, when individuals do this sort of thing, they are *probably* OK, since it is not worth suing individuals. On the other hand, when that individual widely publishes the work, that's upping the risk a LOT over just doing it yourself for yourself (which after all may well be fair use -- up to a court to say -- and if you ask for RD's non-binding opinion on what ought to be, this *should* be fair use). The reason I am making these points here is not because I suspect a real problem in this particular case (it is a reasonable guess that the original author, undoubtedly not himself being an expert in such matters, just assumed that by putting the material out without any kind of notice he was establishing an implicit permission. That's wrong, there is no such procedure, but probably Wes was right in guessing the intention). My point was that these days, with so much stuff floating around the net, you have to be very careful that you *know* what you are picking up. Once again, for personal use, in practice (and maybe in law, depending on how fair use is interpreted), there is nothing to worry about, but when you start publishing stuff to others, or using the material in any kind of commercial endeavor, then you can be in deep water very fast. Consider the following. Suppose you reverse engineer Microsoft Power Point and fix a bug. If you use that just for yourself, then a) Microsoft won't know about it and won't bother you b) It may well be that there is no copyright violation here and that a jury would decide this is fair use, whatever the microsoft license says (I would not imagine a jury being sympathetic to Microsoft claiming that you were not allowed to fix such an error for your own use). But if you publish this modified/fixed version, MS may definitely come after you. Whether they will sue rather than just pressure you to cease and desist is a matter of circumstances and how deep your pockets are. For example, if you are a competitor and make a rival package and on your web site it says "For those whose bosses insist on using powerpoint, and who can't stand dealing with xyz error, we have posted a fixed version of powerpoint. We sympathize with you having to use this inferior software, but at least this fixed version will make one serious headache go away, sorry we can't do anything about the rest [except persuade you to abandon the dark side and use our product :-)]" Then I would bet that Microsoft would sue :-) :-) The other point is that copyright assignment is not something you can just do out of the blue. It must be done by formal agreement. In fact the FSF will only accept copyright assignments under very stringent conditions (including a willingness to provide certain forms of indemnification, and also the FSF has to be convinced that it wants the copyrights). For example, in the case of GNAT, the original version done at NYU was assigned to the FSF through a formal agreement between the FSF and NYU (this assignment was required by the government contract -- an unusual requirement for such a contract). THe ongoing assignment of parts of the GNAT technology by ACT to the FSF comes from a separate agreement. Of course you can always choose any license to use for your own stuff, and you can use the GPL or GMGPL freely, without assigning your copyright. It really is important for people to be careful here. I have come across all sorts of unfortunate cases. In one big project they were using a version of CYGWIN that GPL'ed but not LGPL'ed (or using any other similar license). They were clearly in a situation of having violated Cygnus/Redhat copyrights. I told them they had better contact Redhat and get a commercial license, whether they did I do not know! Robert Dewar ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: More on copyright, (Re: TO WHOM IT MAY CONCERN) 2002-05-02 12:27 ` More on copyright, (Re: TO WHOM IT MAY CONCERN) Robert Dewar @ 2002-05-08 13:56 ` Wes Groleau 2002-05-08 18:01 ` Robert Dewar 0 siblings, 1 reply; 88+ messages in thread From: Wes Groleau @ 2002-05-08 13:56 UTC (permalink / raw) > > I hereby explicitly claim copyright on all differences > > between that message and the original submission > > But you can't claim copyright here. You have created a > deriviative work without the original authors permission. > That is in itself a copyright violation. You can only I hereby withdraw (without concession either way) from any arguments about whether I violated copyright. I will re-enter that fight if and when someone convinces a court to hear the case. But I _can_ claim copyright on the parts that I did. And I hereby withdraw from any argument on that point. -- Wes Groleau http://freepages.rootsweb.com/~wgroleau ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: More on copyright, (Re: TO WHOM IT MAY CONCERN) 2002-05-08 13:56 ` Wes Groleau @ 2002-05-08 18:01 ` Robert Dewar 2002-05-08 18:31 ` Hyman Rosen 2002-05-09 13:41 ` Wes Groleau 0 siblings, 2 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-08 18:01 UTC (permalink / raw) Wes Groleau <wesgroleau@despammed.com> wrote in message news:<3CD92EA5.2EF45E7D@despammed.com>... > But I _can_ claim copyright on the parts that I did. Not really! You can't just go around creating deriviative works without the original author's permission, since this is in itself a clear copyright violation. At the very least this would cancel out any claim of ownership to the derived product that you might think you have. Example: if you create a version of Lion King with overspoken comments on this Disney film, you are definitely violating Disney's copyright and they will come after you. The question of your own copyright interests in the joint work will hardly arise in this situation. It will be a moot point in the true sense of the word, the court will not need to decide this issue (leaving it moot = arguable, and undecided) because the issue of you violating the copyright will be what comes to the court's attention! ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: More on copyright, (Re: TO WHOM IT MAY CONCERN) 2002-05-08 18:01 ` Robert Dewar @ 2002-05-08 18:31 ` Hyman Rosen 2002-05-09 13:41 ` Wes Groleau 1 sibling, 0 replies; 88+ messages in thread From: Hyman Rosen @ 2002-05-08 18:31 UTC (permalink / raw) Robert Dewar wrote: > Wes Groleau <wesgroleau@despammed.com> wrote in message news:<3CD92EA5.2EF45E7D@despammed.com>... >>But I _can_ claim copyright on the parts that I did. > > Not really! You can't just go around creating deriviative > works without the original author's permission, since this > is in itself a clear copyright violation. For USians, look at <http://www.copyright.gov/circs/circ14.html>. From there, Only the owner of copyright in a work has the right to prepare, or to authorize someone else to create, a new version of that work. That's why the GPL is such a strong and unbeatable license. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: More on copyright, (Re: TO WHOM IT MAY CONCERN) 2002-05-08 18:01 ` Robert Dewar 2002-05-08 18:31 ` Hyman Rosen @ 2002-05-09 13:41 ` Wes Groleau 1 sibling, 0 replies; 88+ messages in thread From: Wes Groleau @ 2002-05-09 13:41 UTC (permalink / raw) > > But I _can_ claim copyright on the parts that I did. > > Not really! You can't just go around creating deriviative > works without the original author's permission, since this That's not what I said. I choose not to participate in the discussion of whether what I copied was legal. But portions were not "copied." I have the right to ask anyone, including the original author, to not copy those portions. That is completely independent of whatever permissions are on the original unchanged item. The above statement is consistent with both information at the library of congress and guidelines issued by my current employer's corporate counsel for material we acquire and then modify. -- Wes Groleau http://freepages.rootsweb.com/~wgroleau ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-01 0:54 ` tmoran 2002-05-01 9:42 ` Florian Weimer 2002-05-01 12:43 ` Robert Dewar @ 2002-05-01 12:46 ` Robert Dewar 2002-05-01 18:22 ` OT:Copyright, was " tmoran 2 siblings, 1 reply; 88+ messages in thread From: Robert Dewar @ 2002-05-01 12:46 UTC (permalink / raw) tmoran@acm.org wrote in message news:<11Hz8.4180$PE6.2467133575@newssvr21.news.prodigy.com>... > Maybe someone will e-mail all Simtel material authors suggesting they > register, sue everyone who picks up the bait, and pay a finder's fee to > the e-mailer, who will then get rich. ;) An interesting point. Copyright is odd in that it's strict liability. If you had access, and you copied someone elses material without permission, then it is not a defence to say you could not have known it was copyrighted. Furthermore, the penalty is statutory, and you do not have to show economic harm. For an example, consider the case against mp3.com, where they were assessed the statutory penalty for each ripped CD, and the plaintiff did not bother to even claim, let alone show, economic damage. ^ permalink raw reply [flat|nested] 88+ messages in thread
* OT:Copyright, was Re: Generation of permutations 2002-05-01 12:46 ` Generation of permutations Robert Dewar @ 2002-05-01 18:22 ` tmoran 2002-05-01 21:56 ` Robert Dewar 0 siblings, 1 reply; 88+ messages in thread From: tmoran @ 2002-05-01 18:22 UTC (permalink / raw) > An interesting point. Copyright is odd in that it's strict liability. If > you had access, and you copied someone elses material without permission, > then it is not a defence to say you could not have known it was copyrighted. I wonder if the idea of an "attractive nuisance" would apply. If I post code on c.l.a. with no copyright notice, wait till someone uses it, then sue them, I suspect a judge might be convinced to look askance at my actions. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: OT:Copyright, was Re: Generation of permutations 2002-05-01 18:22 ` OT:Copyright, was " tmoran @ 2002-05-01 21:56 ` Robert Dewar 2002-05-01 23:45 ` tmoran 0 siblings, 1 reply; 88+ messages in thread From: Robert Dewar @ 2002-05-01 21:56 UTC (permalink / raw) tmoran@acm.org wrote in message news:<FnWz8.4425$eZ6.2697016331@newssvr21.news.prodigy.com> > it, then sue them, I suspect a judge might be convinced > to look askance at my actions. The law is based on statute and on precedence of case law, not on Tom Moran's suspicions. After all, consider the case of the lawyer who bought a dozen rare cigars and insured them against all loss. He then smoked them, and claimed insurance on the grounds that they had been consumed in separate small fires. The insurance company refused to pay up. The lawyer sued. Now I would not be surprised if the principle of TMS (Tom Moran Suspicions [as to what the law should be]) would expect the judge to throw the case out. But in fact the judge ruled that the contract did not exempty this case of fire, and the insurance company had to pay $15,000. (the end of this story is that the lawyer was then charged with 12 counts of arson -- you can't go around deliberately burning up your property to collect the insurance. He was found guilty, sentenced to 24 months probation, and ordered to pay a fine of $24,000 :-) This story is reported as true in a competition to find the most notorious case of strange law. But anyway, anyone counting on being protected for copyright violation by appealing to TMS is taking a risk! ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: OT:Copyright, was Re: Generation of permutations 2002-05-01 21:56 ` Robert Dewar @ 2002-05-01 23:45 ` tmoran 2002-05-02 11:58 ` Robert Dewar 0 siblings, 1 reply; 88+ messages in thread From: tmoran @ 2002-05-01 23:45 UTC (permalink / raw) > The law is based on statute and on precedence of case law, > not on Tom Moran's suspicions. For an alternate view, I cite "The life of the law has not been logic; it has been experience.", and "The prophecies of what the courts will do in fact, and nothing more pretentious, are what I mean by the law." and "the only question for the lawyer is, how will the judges act?" Oliver Wendell Holmes, Jr. > After all, consider the case of the lawyer who bought a > ... > This story is reported as true in a competition to find the > most notorious case of strange law. Suggesting, if true, that some judges, some of the time, are very difficult to predict. OTOH, > (the end of this story is that the lawyer was then charged > with 12 counts of arson -- you can't go around deliberately So perhaps the "judge's strange decision" part was taken out of context, and a wiser lawyer would have predicted the judge's determination, with its final result of the insurance company keeping its money and the lawyer going to jail. ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: OT:Copyright, was Re: Generation of permutations 2002-05-01 23:45 ` tmoran @ 2002-05-02 11:58 ` Robert Dewar 0 siblings, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-02 11:58 UTC (permalink / raw) tmoran@acm.org wrote in message news:<I6%z8.150$UZ1.91120865@newssvr13.news.prodigy.com>... > > The law is based on statute and on precedence of case law, > > not on Tom Moran's suspicions. > For an alternate view, I cite "The life of the law has not been logic; > it has been experience.", and "The prophecies of what the courts will do > in fact, and nothing more pretentious, are what I mean by the law." and > "the only question for the lawyer is, how will the judges act?" Oliver > Wendell Holmes, Jr. Tom, please consult the case law in the area of copyright, or a good text book on IPR issues, you are really very wrong here. It is one thing when you give technical advice that is wrong on Ada matters, another when you suggest to people that they can violate copyrights with impunity :-) ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-04-30 22:57 ` Robert Dewar 2002-05-01 0:54 ` tmoran @ 2002-05-01 14:55 ` Wes Groleau 2002-05-02 12:41 ` Robert Dewar 1 sibling, 1 reply; 88+ messages in thread From: Wes Groleau @ 2002-05-01 14:55 UTC (permalink / raw) > > -- The original author claimed no copyright. In order to protect > > -- what seemed to be his intent, I am assigning copyright to the > > -- Free Software Foundation with the condtions below. I reserve the > > -- right to revoke this assignment if and when requested by the > > -- original author. > > This doesn't sound like legal stuff (tedious or otherwise) to me, it sounds > like a clear copyright violation. A lot of people (the writer of the above > presumably included) are under the illusion that an author must explicitly > "claim" copyright by including an explicit copyright message. This is totally > false under current law. All material is copyrighted unless the author > explicitly disclaims copyright. Poorly worded, I'll grant you. He did not claim copyright, nor did he disclaim it, unless you consider putting it on SIMTEL-20 (or allowing it to be put there) to be releasing rights. He also did not reply to e-mail inquiries that did not bounce. > Only the author of a piece of software can offer to assign the copyright As the author of the changes, I could have put better wording on it, true. > By copying this software without taking the trouble to check on the status, See above. > copyright. At $50,000 each, the statutory penalty for copyright violation, it > sounds like the author can get rich. :-) Note that it is not a defense to Having been on the plaintiff's side, I can assure you that it _is_ a defense to point out that the plaintiff knowingly ignored numerous similar offenses before jumping on one of them. (Although that was not "intellectual" property, so a court could say the situation is different. Last I heard, that applied in the U.S. IF it was registered at the Library of Congress. Of course, the fine then was $10,000, so the conditions may have also changed. So, form your own opinion, take your own risk. -- Wes Groleau http://freepages.rootsweb.com/~wgroleau ^ permalink raw reply [flat|nested] 88+ messages in thread
* Re: Generation of permutations 2002-05-01 14:55 ` Wes Groleau @ 2002-05-02 12:41 ` Robert Dewar 0 siblings, 0 replies; 88+ messages in thread From: Robert Dewar @ 2002-05-02 12:41 UTC (permalink / raw) Wes Groleau <wesgroleau@despammed.com> wrote in message news:<3CD001D9.286614CC@despammed.com>... > Poorly worded, I'll grant you. He did not claim copyright, nor did he > disclaim it, unless you consider putting it on SIMTEL-20 (or allowing it > to be put there) to be releasing rights. He also did not reply to > e-mail inquiries that did not bounce. He does not have to "claim copyright". Putting something on the net does not automatically release rights! > As the author of the changes, I could have put better wording > on it, true. The point is that you can't even make the changes without permission >> By copying this software without taking the trouble to check on the status, > > See above. You cannot assume no answer is a negative answer. If you send a letter to Disney saying "I plan to videotape Lion King next week from my seat in the theater and I am going to put it on my web site. If you do not respond immediately, I will assume that means you are giving me permission.", then that's not good enough :-) > Having been on the plaintiff's side, I can assure you that it > _is_ a defense to point out that the plaintiff knowingly ignored > numerous similar offenses before jumping on one of them. > (Although that was not "intellectual" property, so a court > could say the situation is different. The doctrine of adverse posession, and similar principles probably do apply to intellectual property, though case law is scattered, and I don't know of any case that's fully on target here (I did not do a Westlaw search, so I am going off my own limited knowledge here, any reference to the contrary would be interested). But those kind of principles apply over a long time. The author in this case could reasonably say: I put this out so people can use it in accordance with the copyright law, and in particular so that they can copy it where fair use provisions of the law apply, and as far as I am concerned any personal use is fair use, but if I find IBM has been using it, I will come and get them! > Last I heard, that applied in the U.S. IF it was registered at the > Library of Congress. Of course, the fine then was $10,000, so the > conditions may have also changed. Once again, you can register at any point in the future, while the copyright is still in effect, so that is no protection ^ permalink raw reply [flat|nested] 88+ messages in thread
end of thread, other threads:[~2002-05-25 16:21 UTC | newest] Thread overview: 88+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2002-04-29 11:54 Generation of permutations Reinert Korsnes 2002-04-30 13:52 ` Ted Dennison 2002-04-30 14:20 ` Marin David Condic 2002-05-02 12:32 ` Robert Dewar 2002-05-02 15:47 ` Ted Dennison 2002-05-02 16:16 ` Mark Biggar 2002-05-03 13:04 ` Marin David Condic 2002-05-05 0:52 ` Robert Dewar 2002-05-05 23:11 ` tmoran 2002-05-06 2:13 ` Chad R. Meiners 2002-05-06 13:52 ` Stephen Leake 2002-05-09 17:44 ` Darren New 2002-05-09 18:07 ` Stephen Leake 2002-05-09 20:58 ` Darren New 2002-05-09 23:21 ` tmoran 2002-05-09 23:51 ` Darren New 2002-05-10 3:37 ` tmoran 2002-05-10 3:59 ` Darren New 2002-05-10 13:13 ` Robert Dewar 2002-05-25 16:21 ` Robert I. Eachus 2002-05-09 23:24 ` Robert Dewar 2002-05-09 23:48 ` Robert Dewar 2002-05-10 3:37 ` tmoran 2002-05-10 15:10 ` Chad R. Meiners 2002-05-11 4:04 ` Robert Dewar 2002-05-16 1:35 ` Chad R. Meiners 2002-05-11 4:05 ` Robert Dewar 2002-05-06 15:46 ` Wes Groleau 2002-05-06 16:21 ` Chad R. Meiners 2002-05-06 16:33 ` Darren New 2002-05-07 0:06 ` tmoran 2002-05-07 0:26 ` Darren New 2002-05-07 1:56 ` tmoran 2002-05-07 10:39 ` Robert Dewar 2002-05-07 17:25 ` Chad R. Meiners 2002-05-08 2:27 ` Robert Dewar 2002-05-08 8:44 ` Mats Karlssohn 2002-05-07 17:00 ` Wes Groleau 2002-05-06 21:33 ` Robert Dewar 2002-05-06 17:26 ` Marin David Condic 2002-05-07 7:35 ` tmoran 2002-05-07 13:22 ` Marin David Condic 2002-05-08 5:23 ` tmoran 2002-05-08 14:10 ` Marin David Condic 2002-05-09 16:20 ` Darren New 2002-05-09 19:04 ` tmoran 2002-05-08 16:20 ` Darren New 2002-05-08 17:31 ` tmoran 2002-05-08 17:39 ` Chad R. Meiners 2002-05-07 15:34 ` Darren New 2002-05-07 17:44 ` Chad R. Meiners 2002-05-07 19:58 ` tmoran 2002-05-07 21:05 ` Turing-undecidable languages (OT) Chad R. Meiners 2002-05-08 8:24 ` Danx 2002-05-08 17:16 ` Chad R. Meiners 2002-05-10 2:37 ` Robert Dewar 2002-05-08 9:16 ` Dmitry A. Kazakov 2002-05-08 17:18 ` Chad R. Meiners 2002-05-09 20:56 ` Dmitry A.Kazakov 2002-05-09 16:18 ` Chad R. Meiners 2002-05-10 2:52 ` Robert Dewar 2002-05-08 2:17 ` Generation of permutations Robert Dewar 2002-05-03 13:13 ` Ted Dennison 2002-05-03 13:24 ` Lutz Donnerhacke 2002-04-30 15:06 ` Hyman Rosen 2002-05-01 8:40 ` Adrian Hoe 2002-05-01 19:53 ` Hyman Rosen 2002-05-11 1:52 ` Steven Deller 2002-05-02 16:24 ` Mark Biggar 2002-04-30 17:12 ` Wes Groleau 2002-04-30 22:57 ` Robert Dewar 2002-05-01 0:54 ` tmoran 2002-05-01 9:42 ` Florian Weimer 2002-05-02 12:34 ` Robert Dewar 2002-05-01 12:43 ` Robert Dewar 2002-05-01 15:05 ` TO WHOM IT MAY CONCERN Wes Groleau 2002-05-02 12:27 ` More on copyright, (Re: TO WHOM IT MAY CONCERN) Robert Dewar 2002-05-08 13:56 ` Wes Groleau 2002-05-08 18:01 ` Robert Dewar 2002-05-08 18:31 ` Hyman Rosen 2002-05-09 13:41 ` Wes Groleau 2002-05-01 12:46 ` Generation of permutations Robert Dewar 2002-05-01 18:22 ` OT:Copyright, was " tmoran 2002-05-01 21:56 ` Robert Dewar 2002-05-01 23:45 ` tmoran 2002-05-02 11:58 ` Robert Dewar 2002-05-01 14:55 ` Wes Groleau 2002-05-02 12:41 ` Robert Dewar
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox