From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c42dbf68f5320193 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-05-09 11:14:25 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!hammer.uoregon.edu!skates!not-for-mail From: Stephen Leake Newsgroups: comp.lang.ada Subject: Re: Generation of permutations Date: 09 May 2002 14:07:21 -0400 Organization: NASA Goddard Space Flight Center (skates.gsfc.nasa.gov) Message-ID: References: <5ee5b646.0205041652.63032ba6@posting.google.com> <3CDAB578.6F32339D@san.rr.com> NNTP-Posting-Host: anarres.gsfc.nasa.gov Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: skates.gsfc.nasa.gov 1020968031 12622 128.183.220.71 (9 May 2002 18:13:51 GMT) X-Complaints-To: usenet@news.gsfc.nasa.gov NNTP-Posting-Date: 9 May 2002 18:13:51 GMT User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 Xref: archiver1.google.com comp.lang.ada:23794 Date: 2002-05-09T18:13:51+00:00 List-Id: Darren New 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