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-Thread: 103376,93a8020cc980d113 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Newsgroups: comp.lang.ada Subject: Re: What is wrong with Ada? 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> <13tcswu59l28h.zxb26cabf9a0.dlg@40tude.net> <15k5b4j6za8ag.tpkuccinvzbd.dlg@40tude.net> From: Markus E Leypold Organization: N/A Date: Mon, 16 Apr 2007 01:06:28 +0200 Message-ID: User-Agent: Some cool user agent (SCUG) Cancel-Lock: sha1:dZv6iO31Ymz60ILLzGQZFs4eTxQ= MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii NNTP-Posting-Host: 88.72.204.228 X-Trace: news.arcor-ip.de 1176677937 88.72.204.228 (16 Apr 2007 00:58:57 +0200) X-Complaints-To: abuse@arcor-ip.de Path: g2news1.google.com!news1.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!newsfeed.arcor-ip.de!news.arcor-ip.de!not-for-mail Xref: g2news1.google.com comp.lang.ada:15068 Date: 2007-04-16T01:06:28+02:00 List-Id: "Dmitry A. Kazakov" writes: > On Sun, 15 Apr 2007 18:01:10 +0200, Markus E Leypold wrote: > >> Now I'd like you to close this loophole for arbitrary hand waving and >> define NON-TRIVIAL in a way suitable to you purposes (but keep it >> convincing, still -- defining it to FALSE won't wash with me) and >> perhaps try to prove the central assertion above. > > OK, here is a formalization of "non-trivial." Let me use a more or less > standard notation: > > IN is the set of input states (the language over a finite alphabet A) > S is the set of states > s1 is the initial state > T : S x A -> S is the transition function > OUT = the set of output states (a subset of S, which we don't care) > > def: Closure of T > ---------------------- > Let a=(a' a'' a''' a'''' ... a*) be a finite input from IN. > > P(a)=T(a*, ... T(a''', T(a'', T(a', s1)))) > > Informally P(a) is the state to which a would bring the machine. > > P : IN -> S > > def: Equivalent input states (strings) > --------------------------------------------- > a, b of IN are called equivalent iff P(a)=P(b). > > Let's denote non-equivalent states as a#b > > (P was defined on finite strings of IN. Defining it in some reasonable way > for infinite cases would require efforts, which I don't want to run into.) > > def: Non-trivial input (language) > -------------------------------------- > IN is non-trivial iff for any finite subset {a1, a2, a3,..., aN} of IN > there exits an input string b in IN such that forall i=1..N b#ai. > > From this definition immediately follows that any machine handling > non-trivial input will necessarily have infinite S. > > A classical example > > ab > aabb > aaabbb > aaaabbbb > ... > > can serve as one of non-trivial input. > > Other three I have mentioned in my previous posts: counting integers, > recognizing irrational numbers, summation of infinite series 1-1+1-1+1... > (aka Tompson's lamp). > > P.S. This does not apply to Robert's example, because he considered a set > of machines with individual machines parametrized by some number which > influences the number of states. On second thought your "proof" is not so far of the mark. Indeed, you've proven that one cannot implement a certain class of algorithms on finite machines. You call those (and only those) non-trivial. Your original statement > 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. ] though. suggests (to me) another meanning of non trivial than just "requires inifinitely many states". I'd have expected something more motivated from the everyday use of the word trivial. But be that as it may be: I only have to ask from you the favor, that you don't spread the results of your research further, probably refrain from publishing. Yes I know, science must publish and all that, but consider, what will happen when our customers find out, that all we do or even CAN do for them, is to implement _trivial_ data processing, since they still have finite machines. You'll destroy -- single handely -- a whole branch of industry. I know you never have held much regard for computer science (Quote: 'And that is because CS is not much science. It rather sways between applied mathematics and "stamp collecting"'), so they probably had it coming, but consider the repercussions (hungry children, so called programmers jumping from the top floors of sky scrapers, hitting innocent by standers -- all the tragedy. So - please - show some mercy and keep it silent. ;-) Regards -- Markus > > -- > Regards, > Dmitry A. Kazakov > http://www.dmitry-kazakov.de