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,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.107.198.204 with SMTP id w195mr17575883iof.4.1467373732369; Fri, 01 Jul 2016 04:48:52 -0700 (PDT) X-Received: by 10.157.29.3 with SMTP id m3mr781634otm.2.1467373732340; Fri, 01 Jul 2016 04:48:52 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!news.glorb.com!r1no8261475ige.0!news-out.google.com!o189ni13784ith.0!nntp.google.com!jk6no8239538igb.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Fri, 1 Jul 2016 04:48:51 -0700 (PDT) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=2601:191:8202:8510:5985:2c17:9409:aa9c; posting-account=fdRd8woAAADTIlxCu9FgvDrUK4wPzvy3 NNTP-Posting-Host: 2601:191:8202:8510:5985:2c17:9409:aa9c References: <57346ac8$0$4570$426a74cc@news.free.fr> <57707888$0$5274$426a34cc@news.free.fr> <43a09f40-fdea-461e-9b0a-4419b86c1a56@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Ada.Strings.Fixed.Count raises Storage_Error From: rieachus@comcast.net Injection-Date: Fri, 01 Jul 2016 11:48:52 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Xref: news.eternal-september.org comp.lang.ada:30989 Date: 2016-07-01T04:48:51-07:00 List-Id: On Wednesday, June 29, 2016 at 3:57:47 PM UTC-4, Dmitry A. Kazakov wrote: > Goedel results don't apply to programs anyway, because you are not=20 > required to decide anything using the program at hand. You are free to=20 > use *another* program, so you can break out. Sigh! G=C3=B6del proved not just that there are systems where some function= s cannot be computed correctly, but that there are functions which cannot b= e computed correctly by any system. There are systems which are not powerf= ul enough to try to compute these functions, but those systems are very lim= ited. Regular expressions are an example of such a limited system, Ada com= pilers are not. =20 > Nor the Halting problem does apply. For any program having a finite=20 > number of states, one clearly can decide in finite time with finite=20 > storage whether the program halts. Since when have Ada compilers dealt with only finite states?* There are pr= ogramming languages which do have such limits, but Fortran, PL/I, Ada, C++,= and other general purpose programming languages are not among them. It is= nice to think you live inside a little box, but Ada compilers can (and do)= deal with programs in chunks called compilation units, and programs can be= extended over multiple physical processors, each of which can accept exter= nal files as input. To be explicit, theorem proving systems are attempts to solve the halting p= roblem. You hope that your theorem prover will give a correct answer or gi= ve up, but the reality is that there are programs that are never handed to = theorem provers because they will execute "forever" without finding an answ= er. Ada 80 had a statement that compilers were expected to find a valid elabora= tion order, and if one did not exist, the program was illegal. So I, tongu= e in cheek, wrote a program which was legal if--and only if--Format's Last = Theorem was false. Oops! Rules were changed so that compilers can leave t= hose edge cases until run-time, and for most programs compilers will find a= n elaboration order which does not need to check for elaboration errors. (= So now you can compile that program, and a theorem prover that can handle F= LT can prove that it never halts, or maybe prove that it halts when your bi= gnum package runs out of file storage. ;-) * You may contend that your personal computer has a finite number of states= , but well before you can finish enumerating them, you will upgrade the pro= cessor, memory, and/or disks (whether mechanical or solid state). And then= there are services like Drop Box which enable you to store data "in the cl= oud." So the time when computers had a finite set of states is long past. = (Even Univac I, with 1000 words of memory, had ten tape drives, and an ope= rator to mount new tapes when required.)