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 Mon, 16 Apr 2007 00:00:11 +0200, Markus E Leypold wrote:
>
>> "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.
>> 
>> I can't believe it, but you really succeeded to muddle the issue at
>> hand -- again.
>> 
>> Your assertion was, that "... programs, which <something about non
>> trivial processing> are wrong", aka cannot be implemented on a finite
>> machine. "Wrong" in my world means: Don't conform to specification.
>
> def, Specification
> ------------------------
> Given the language IN (over a finite alphabet A) and OUT, the set of output
> states.
>
> 1. P exists on IN
>
> 2. P(IN) in OUT (= forall s in IN, P(s) in OUT)
>
> def. Program
> ------------------
> A program is the triplet {s1, S, T} (the initial state, the set of states,
> the transition function).
>
>> But -- you're not talking about specifications at all in your
>> formalization: You talk about programs and only about programs.
>
> Because my initial statement was about processing and the states of. When
> processing is impossible, then whatever specification it should fulfill, it
> does not.

I already granted that point -- still, I don't like when people change
the rules implicitely.

>
>> My challenge still stands: Define a sutiable predicate NON-TRIVIAL on
>> _the specification_.
>
> I did. Consider OUT instead of whole S.


>> What you prove (at first glance) is something completely
>> different. You prove that programs that have a certain property (which
>> you explained and call "non trivial") cannot be _implemented_ on
>> finite machines. Since real machines are finite, every real program is
>> trivial. This obviously is bollocks or at least a rather unusual
>> definition of trivial.

> I called it trivial because a valid program processing an infinite input
> would not require *all* the input to finish. 

(Hm, what is "valid"? You keep introducing new predicates into the
discussion all the time which are undefined so far and only serve to
twist the rules later, I suspect.)

Sorry, that is nonsense. Take the program which just determines wether
the length of a finite sequence ending with EOI is even or odd. (1)
It's trivial by your definition, (2) it requires (obviously) the
complete input sequence to give the right answer, (3) it CAN be
implemented on a finite machine and (4) it has an infinite set of
possible inputs IN.

Of course it doesn't stop or give a useful answer on sequences that
are not in IN (don't end with the proper end-of-input symbol), but
this is exactly why I took the pain to distinguish between the spec SP
and the program P, which is not required to give any meaningful
results when fed with input outside the spec.

My suspicion is you're mixing up (a) "inifinite input sequences"
(i.e. input items consisting of an inifinite number of input symbols)
with (b) "inifinite set of possible inputs".  I'm sorry if I can't
formulate that more precisely in plain english: One of the reasons I
tried a methamatical notation, but you had to switch horses and
incompletely at that.

The latter case (b) would be card(IN) is infinite (countable in our
case, since S is countable, IN \subset seq[S] and seq(S), the set of
all finite sequences from symbols in S is countable), in my
notation. The first case (a) is not contained in IN ever (in my
model) since I'm not talking about infinite sequences one has to read
out the result some time (at the end of the input sequence).

> So the ratio
> card(S)/card(IN)=0. We can use some other word instead of "trivial," if
> that is reserved for "I can understand this code after three beers..." 

I repeat again: According to your definition all real programs on real
machines are "trivial". So you can understand them all after three
beers? I bow before your superiority, super human Dmitry A. Kazakov
(but if that mixture of bad science and bragging continues, won't be
able to take you serious for much longer).

Regards -- Markus