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!newsfeed01.sul.t-online.de!t-online.de!news.belwue.de!newsfeed.arcor.de!newsspool1.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> <13tcswu59l28h.zxb26cabf9a0.dlg@40tude.net> Date: Sun, 15 Apr 2007 19:51:11 +0200 Message-ID: <15k5b4j6za8ag.tpkuccinvzbd.dlg@40tude.net> NNTP-Posting-Date: 15 Apr 2007 19:50:14 CEST NNTP-Posting-Host: f3a9a94a.newsspool2.arcor-online.net X-Trace: DXC=R3@X5POK79Z@@RW1FjIB5SA9EHlD;3YcR4Fo<]lROoRQ8kF 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. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de