Re: What is wrong with Ada?

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

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.

> 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. 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..." 

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de