Generation of permutations

Generation of permutations

[Reinert Korsnes]

Hi,

Are there any good (Ada95) packages for generation of permutations 
(of elements in array) ?

reinert

Re: Generation of permutations

[Ted Dennison]

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

Re: Generation of permutations

[Marin David Condic]

"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

Re: Generation of permutations

[Hyman Rosen]

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.

Re: Generation of permutations

[Wes Groleau]

> 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

Re: Generation of permutations

[Robert Dewar]

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

Re: Generation of permutations

[tmoran]

> 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. ;)

Re: Generation of permutations

[Adrian Hoe]

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

Re: Generation of permutations

[Florian Weimer]

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.

Re: Generation of permutations

[Robert Dewar]

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.

Re: Generation of permutations

[Robert Dewar]

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.

Re: Generation of permutations

[Wes Groleau]

> > --    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

TO WHOM IT MAY CONCERN

[Wes Groleau]

> 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

OT:Copyright, was Re: Generation of permutations

[tmoran]

> 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.

Re: Generation of permutations

[Hyman Rosen]

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.

Re: OT:Copyright, was Re: Generation of permutations

[Robert Dewar]

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!

Re: OT:Copyright, was Re: Generation of permutations

[tmoran]

> 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.

Re: OT:Copyright, was Re: Generation of permutations

[Robert Dewar]

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 :-)

More on copyright, (Re: TO WHOM IT MAY CONCERN)

[Robert Dewar]

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

Re: Generation of permutations

[Robert Dewar]

"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.

Re: Generation of permutations

[Robert Dewar]

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.

Re: Generation of permutations

[Robert Dewar]

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

Re: Generation of permutations

[Ted Dennison]

"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

Re: Generation of permutations

[Mark Biggar]

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

Re: Generation of permutations

[Mark Biggar]

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

Re: Generation of permutations

[Marin David Condic]

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.
>

Re: Generation of permutations

[Ted Dennison]

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

Re: Generation of permutations

[Lutz Donnerhacke]

* 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)

Re: Generation of permutations

[Robert Dewar]

"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

Re: Generation of permutations

[tmoran]

> 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.

Re: Generation of permutations

[Chad R. Meiners]

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.

Re: Generation of permutations

[Stephen Leake]

"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

Re: Generation of permutations

[Wes Groleau]

> > > 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

Re: Generation of permutations

[Chad R. Meiners]

"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

Re: Generation of permutations

[Darren New]

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%.

Re: Generation of permutations

[Marin David Condic]

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.
>

Re: Generation of permutations

[Robert Dewar]

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 :-)

Re: Generation of permutations

[tmoran]

> ... 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?"
?

Re: Generation of permutations

[Darren New]

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%.

Re: Generation of permutations

[tmoran]

> 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.

Re: Generation of permutations

[tmoran]

> "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.

Re: Generation of permutations

[Robert Dewar]

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 :-)

Re: Generation of permutations

[Marin David Condic]

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.

Re: Generation of permutations

[Darren New]

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%.

Re: Generation of permutations

[Wes Groleau]

> 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

Re: Generation of permutations

[Chad R. Meiners]

"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.

Re: Generation of permutations

[Chad R. Meiners]

<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.

Re: Generation of permutations

[tmoran]

> >   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

Turing-undecidable languages (OT)

[Chad R. Meiners]

<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

Re: Generation of permutations

[Robert Dewar]

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.

Re: Generation of permutations

[Robert Dewar]

> 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 :-)

Re: Generation of permutations

[tmoran]

> 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.

Re: Turing-undecidable languages (OT)

[Danx]

"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

Re: Generation of permutations

[Mats Karlssohn]

"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

Re: Turing-undecidable languages (OT)

[Dmitry A. Kazakov]

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

Re: More on copyright, (Re: TO WHOM IT MAY CONCERN)

[Wes Groleau]

> > 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

Re: Generation of permutations

[Marin David Condic]

<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

Re: Generation of permutations

[Darren New]

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%.

Re: Turing-undecidable languages (OT)

[Chad R. Meiners]

"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.

Re: Turing-undecidable languages (OT)

[Chad R. Meiners]

"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.

Re: Generation of permutations

[tmoran]

> > 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.

Re: Generation of permutations

[Chad R. Meiners]

"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.

Re: More on copyright, (Re: TO WHOM IT MAY CONCERN)

[Robert Dewar]

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!

Re: More on copyright, (Re: TO WHOM IT MAY CONCERN)

[Hyman Rosen]

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.

Re: More on copyright, (Re: TO WHOM IT MAY CONCERN)

[Wes Groleau]

> > 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

Re: Turing-undecidable languages (OT)

[Chad R. Meiners]

"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.

Re: Generation of permutations

[Darren New]

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%.

Re: Generation of permutations

[Darren New]

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%.

Re: Generation of permutations

[Stephen Leake]

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

Re: Generation of permutations

[tmoran]

> > 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.

Re: Turing-undecidable languages (OT)

[Dmitry A.Kazakov]

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

Re: Generation of permutations

[Darren New]

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%.

Re: Generation of permutations

[tmoran]

> 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".)

Re: Generation of permutations

[Robert Dewar]

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

Re: Generation of permutations

[Robert Dewar]

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.

Re: Generation of permutations

[Darren New]

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%.

Re: Turing-undecidable languages (OT)

[Robert Dewar]

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.

Re: Turing-undecidable languages (OT)

[Robert Dewar]

"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 :-)

Re: Generation of permutations

[tmoran]

> 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.

Re: Generation of permutations

[tmoran]

> > 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

Re: Generation of permutations

[Darren New]

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%.

Re: Generation of permutations

[Robert Dewar]

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 :-)

Re: Generation of permutations

[Chad R. Meiners]

"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.

RE: Generation of permutations

[Steven Deller]

[-- 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 ;

Re: Generation of permutations

[Robert Dewar]

"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.

Re: Generation of permutations

[Robert Dewar]

"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).

Re: Generation of permutations

[Chad R. Meiners]

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

Re: Generation of permutations

[Robert I. Eachus]

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. ;-)