Re: What is wrong with Ada?

[Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de>]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> 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