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=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,93a8020cc980d113 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news2.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!t-online.de!news.karotte.org!news2.arglkargh.de!noris.net!newsfeed.arcor.de!newsspool3.arcor-online.net!news.arcor.de.POSTED!not-for-mail From: "Dmitry A. Kazakov" Subject: Re: What is wrong with Ada? Newsgroups: comp.lang.ada User-Agent: 40tude_Dialog/2.0.15.1 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Reply-To: mailbox@dmitry-kazakov.de Organization: cbb software GmbH References: <1176150704.130880.248080@l77g2000hsb.googlegroups.com> <461B52A6.20102@obry.net> <461BA892.3090002@obry.net> <82dgve.spf.ln@hunter.axlog.fr> <1176226291.589741.257600@q75g2000hsh.googlegroups.com> <4eaive.6p9.ln@hunter.axlog.fr> <1rbtw92apxpl1.1ednvo8v6oiq8$.dlg@40tude.net> Date: Sun, 15 Apr 2007 15:41:46 +0200 Message-ID: <13tcswu59l28h.zxb26cabf9a0.dlg@40tude.net> NNTP-Posting-Date: 15 Apr 2007 15:40:50 CEST NNTP-Posting-Host: 07d9c321.newsspool3.arcor-online.net X-Trace: DXC=f1ZiE6K\BH3YRnXiMRfGjG2[DNcfSJ;bb[UIRnRBaCd On Sat, 14 Apr 2007 12:48:12 +0200, Markus E Leypold wrote: > "Dmitry A. Kazakov" writes: > >> What I meant is that we cannot write a correct program running on a finite >> machine which would non-trivially processes an infinite input. [ <=> >> uncountable sets cannot be enumerated. ] > > That is, excuse me, wrong. I thought that you had fallen for that > fallacy. Let me explain: > > The machine itself might go only through a finite number of > states. But the user input might be a sequence of key presses that > might terminate arbitrarily late. The input is finite, but the > "processing state space" and the output space are only finite. This is > possible: Imagein a "machine" that only counts/indicates wether the > number of keypresses entered in a sequence from power-on to the end of > sequence mark are odd or even: Finite program, finite states (rather > easy indeed). But the set of all "legal" input sequences is > infinite. Nonetheless the program is correct. Which is an example of trivial processing. >> Consider a program P that counts the number of key presses. This program is >> necessarily incorrect. Because a correct P would have an infinite number of >> states. > > In this case yes. But see above. Logically an example that shows an > attempt to produce an artefact with property X (your program) that > fails, does not prove its impossible. Hmm, that counting infinite sequences is incomputable in DFA barely requires a formal proof... > I've shown that your proposition > doesn't hold (except if you define "non-trivially" as requiring an > infinete number of "processing states". Yes I do. Trivial means that the set of all possible input states could be broken into a finite set of classes of equivalent states. In your case into just two sets of odd and even sequences of key presses. Trivial infiniies are fake ones. BTW, your example could be made non-trivial, see Thomson's lamp. Which shows that even trivial inputs don't ensure that the number of computational states can be finite. It is a necessary but insufficient condition. Consider an input of decimal digits. The objective is to determine whether it composes an irrational number. Obviously any sequence is either rational or not. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de