Re: What is wrong with Ada?

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

On Sat, 14 Apr 2007 12:48:12 +0200, Markus E Leypold wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> 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. ]
> 
> That is, excuse me, wrong. I thought that you had fallen for that
> fallacy. Let me explain:
> 
> The machine itself might go only through a finite number of
> states. But the user input might be a sequence of key presses that
> might terminate arbitrarily late. The input is finite, but the
> "processing state space" and the output space are only finite. This is
> possible: Imagein a "machine" that only counts/indicates wether the
> number of keypresses entered in a sequence from power-on to the end of
> sequence mark are odd or even: Finite program, finite states (rather
> easy indeed). But the set of all "legal" input sequences is
> infinite. Nonetheless the program is correct.

Which is an example of trivial processing.

>> Consider a program P that counts the number of key presses. This program is
>> necessarily incorrect. Because a correct P would have an infinite number of
>> states.
> 
> In this case yes. But see above. Logically an example that shows an
> attempt to produce an artefact with property X (your program) that
> fails, does not prove its impossible.

Hmm, that counting infinite sequences is incomputable in DFA barely
requires a formal proof...

> I've shown that your proposition
> doesn't hold (except if you define "non-trivially" as requiring an
> infinete number of "processing states".

Yes I do. Trivial means that the set of all possible input states could be
broken into a finite set of classes of equivalent states. In your case into
just two sets of odd and even sequences of key presses. Trivial infiniies
are fake ones.

BTW, your example could be made non-trivial, see Thomson's lamp. Which
shows that even trivial inputs don't ensure that the number of
computational states can be finite. It is a necessary but insufficient
condition. Consider an input of decimal digits. The objective is to
determine whether it composes an irrational number. Obviously any sequence
is either rational or not.
 
-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de