From: Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de>
Subject: Re: What is wrong with Ada?
Date: Sat, 14 Apr 2007 12:48:12 +0200
Date: 2007-04-14T12:48:12+02:00 [thread overview]
Message-ID: <mn3b33w7tf.fsf@hod.lan.m-e-leypold.de> (raw)
In-Reply-To: el1sx203zohn$.1ehb1vbs3p0vd.dlg@40tude.net
"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> On Fri, 13 Apr 2007 02:16:56 +0200, Markus E Leypold wrote:
>
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>
>>> Tests should cover all program states. Covering all paths is a rough
>>> approximation of.
>>
>>> But the number of program states is finite, or else the program is wrong
>>> anyway?
>>
>> Don't understand that. Assuming the program terminates fo a give input
>> I the number of states it goes through during execution -- S_1 ... S_n
>> -- is finite. The number of valid input sets is usually less well
>> defined, but assuming (and this is wrong) they are finite, i.e. the
>> sets I \from I_1, I_2 ... I_n are the only valid input then you still
>> have a finite number of program states. Still the number of possible
>> inputs might be rather large (i.e. to a type setter it's all possible
>> books :-), so exhaustive testing is impossible (and your "Tests should
>> cover all program states" is just saying, that you can't test enough).
>>
>> But the set of all inputs is not necessarily finite -- i.e. in the
>> case that the user might enter one data item after the other and get
>> some answer about that item until he enters a end-of-input symbol
>> (stupid example: an interactive prime tester). Since it is nonsense to
>> artificially restrict the length of the user interaction just to get a
>> finite set of input sequences, we will have to live with a infinite
>> number of potential inputs to the program. So the paths covered are
>> also inifinite (program state is still finite since the machine has
>> only finite state).
>
> 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.
> 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. I've shown that your proposition
doesn't hold (except if you define "non-trivially" as requiring an
infinete number of "processing states".
> Obviously, for an unlimited input, if you use Integer, you have to deal
> with Constraint_Error, if you use Unbounded_String be prepared to
> Storage_Error [*]. Otherwise the program is not non-testable, it is
> *proven* wrong.
>
> Non-testability is rather practical. For all, if P has n states then a test
> program T(P) should have > 2**n states, and T(T(P)) should have >
> 2**(2**n)...
See above: You're wrong.
Regards -- Markus
next prev parent reply other threads:[~2007-04-14 10:48 UTC|newest]
Thread overview: 147+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-04-09 20:31 What is wrong with Ada? martinbishop
2007-04-10 1:14 ` Chip and Allie Orange
2007-04-10 8:32 ` gautier_niouzes
2007-04-10 18:21 ` Chip Orange
2007-04-10 1:15 ` Jeffrey R. Carter
2007-04-10 9:02 ` Pascal Obry
2007-04-10 14:32 ` Markus E Leypold
2007-04-10 15:09 ` Pascal Obry
2007-04-10 15:39 ` Markus E Leypold
2007-04-10 16:12 ` Jean-Pierre Rosen
2007-04-10 17:31 ` Chad R. Meiners
2007-04-10 18:24 ` Markus E Leypold
2007-04-10 18:28 ` Ludovic Brenta
2007-04-10 20:22 ` Markus E Leypold
2007-04-11 9:40 ` Jean-Pierre Rosen
2007-04-11 11:20 ` Georg Bauhaus
2007-04-11 23:45 ` Brian May
2007-04-12 7:40 ` Jean-Pierre Rosen
2007-04-12 16:44 ` kevin cline
2007-04-12 17:32 ` Pascal Obry
2007-04-12 16:46 ` kevin cline
2007-04-12 17:35 ` Pascal Obry
2007-04-21 2:13 ` adaworks
2007-04-21 9:49 ` Simon Wright
2007-04-21 14:15 ` Markus E Leypold
2007-04-22 7:38 ` adaworks
2007-04-23 1:33 ` Brian May
2007-04-21 18:33 ` adaworks
2007-04-12 18:11 ` Markus E Leypold
2007-04-16 14:25 ` Bob Spooner
2007-04-16 14:50 ` Markus E Leypold
2007-04-17 9:17 ` Pascal Obry
2007-04-17 10:04 ` Georg Bauhaus
2007-04-17 15:02 ` Ed Falis
2007-04-17 15:48 ` Pascal Obry
2007-04-17 20:53 ` Ludovic Brenta
2007-04-18 0:21 ` Jeffrey R. Carter
2007-04-18 8:16 ` Ludovic Brenta
2007-04-21 2:18 ` adaworks
2007-04-12 18:47 ` Robert A Duff
2007-04-12 19:39 ` Dmitry A. Kazakov
2007-04-12 19:54 ` Peter C. Chapin
2007-04-12 20:41 ` Dmitry A. Kazakov
2007-04-14 19:56 ` Chad R. Meiners
2007-04-13 0:16 ` Markus E Leypold
2007-04-14 7:01 ` Dmitry A. Kazakov
2007-04-14 10:48 ` Markus E Leypold [this message]
2007-04-15 13:41 ` Dmitry A. Kazakov
2007-04-15 16:01 ` Markus E Leypold
2007-04-15 17:51 ` Dmitry A. Kazakov
2007-04-15 21:41 ` Markus E Leypold
2007-04-15 22:00 ` Markus E Leypold
2007-04-16 8:26 ` Dmitry A. Kazakov
2007-04-16 9:04 ` Markus E Leypold
2007-04-17 7:58 ` Georg Bauhaus
2007-04-17 9:27 ` Dmitry A. Kazakov
2007-04-17 10:46 ` Markus E Leypold
2007-04-17 10:48 ` Markus E Leypold
2007-04-15 23:06 ` Markus E Leypold
2007-04-22 21:50 ` Markus E Leypold
2007-04-23 19:26 ` Dmitry A. Kazakov
2007-04-23 20:39 ` Ray Blaak
2007-04-24 8:39 ` Dmitry A. Kazakov
2007-04-24 16:43 ` Ray Blaak
2007-04-23 22:02 ` Markus E Leypold
2007-04-14 22:49 ` Robert A Duff
2007-04-14 23:39 ` Markus E Leypold
2007-04-23 21:16 ` Larry Kilgallen
2007-04-23 21:21 ` Ray Blaak
2007-04-23 22:15 ` Markus E Leypold
2007-04-12 21:18 ` Georg Bauhaus
2007-04-13 7:39 ` Stuart
2007-04-13 9:05 ` Georg Bauhaus
2007-04-13 0:10 ` Brian May
2007-04-13 8:55 ` Harald Korneliussen
2007-04-14 22:47 ` Robert A Duff
2007-04-14 19:50 ` Chad R. Meiners
2007-04-14 22:52 ` Robert A Duff
2007-04-14 19:28 ` Chad R. Meiners
2007-04-16 8:50 ` Jean-Pierre Rosen
2007-04-16 9:18 ` Dmitry A. Kazakov
2007-04-16 9:56 ` Markus E Leypold
2007-04-16 16:45 ` Robert A Duff
2007-04-17 9:05 ` Jean-Pierre Rosen
2007-04-17 14:51 ` Robert A Duff
2007-04-22 7:42 ` adaworks
2007-04-10 18:15 ` Markus E Leypold
2007-04-20 16:34 ` adaworks
2007-04-10 19:44 ` Simon Wright
2007-04-10 20:43 ` Markus E Leypold
2007-04-10 22:02 ` Georg Bauhaus
2007-04-10 22:15 ` Markus E Leypold
2007-04-11 8:59 ` Georg Bauhaus
2007-04-20 16:25 ` adaworks
2007-04-20 20:35 ` Markus E Leypold
2007-04-21 5:51 ` adaworks
2007-04-25 0:10 ` Chad R. Meiners
2007-04-10 15:59 ` Jeffrey R. Carter
2007-04-10 16:31 ` Dmitry A. Kazakov
2007-04-10 18:08 ` Markus E Leypold
2007-04-11 23:05 ` kevin cline
2007-04-12 7:55 ` Dmitry A. Kazakov
2007-04-12 10:43 ` Peter C. Chapin
2007-04-12 13:04 ` Markus E Leypold
2007-04-13 10:46 ` Harald Korneliussen
2007-04-13 16:25 ` Adam Beneschan
2007-04-14 23:41 ` Markus E Leypold
2007-04-22 7:54 ` adaworks
2007-04-21 18:50 ` adaworks
2007-04-21 19:53 ` Dmitry A. Kazakov
[not found] ` <H5EWh.6302$H_5.612@newssvr23.news.prodigy.net>
2007-04-22 9:33 ` Dmitry A. Kazakov
2007-04-10 23:43 ` Brian May
2007-04-12 14:25 ` Bob Spooner
2007-04-13 0:22 ` Brian May
2007-04-23 2:25 ` Justin Gombos
2007-05-16 1:29 ` Adrian Hoe
2007-04-10 1:25 ` Brian May
2007-04-10 1:48 ` martinbishop
2007-04-10 8:33 ` gautier_niouzes
2007-04-10 14:58 ` Markus E Leypold
2007-04-10 19:05 ` Randy Brukardt
2007-04-10 20:27 ` Markus E Leypold
2007-04-12 1:18 ` Randy Brukardt
2007-04-12 13:02 ` Markus E Leypold
2007-04-12 8:47 ` Ada vendor FAQ (was: What is wrong with Ada?) Ludovic Brenta
2007-04-11 15:21 ` What is wrong with Ada? Jason King
2007-04-11 17:53 ` tmoran
2007-04-12 18:55 ` Alexander E. Kopilovich
2007-04-13 2:59 ` Jason King
2007-04-13 9:03 ` Georg Bauhaus
2007-04-14 15:28 ` Jason King
2007-04-16 16:48 ` Georg Bauhaus
2007-04-21 12:56 ` AJAskey
2007-04-21 13:50 ` jimmaureenrogers
2007-04-21 14:46 ` AJAskey
2007-04-21 15:43 ` Markus E Leypold
2007-04-23 1:37 ` Brian May
2007-04-21 15:48 ` Markus E Leypold
2007-04-21 21:42 ` jimmaureenrogers
[not found] ` <vzwWh.2452$Ut6.1591@newsread1.news.pas.earthlink.net>
2007-04-22 0:53 ` Markus E Leypold
2007-04-25 0:20 ` Chad R. Meiners
2007-04-25 9:57 ` Markus E Leypold
2007-04-25 11:19 ` Georg Bauhaus
2007-04-25 11:54 ` Markus E Leypold
2007-04-25 13:24 ` Georg Bauhaus
2007-04-25 13:41 ` adaworks
2007-04-26 3:24 ` jimmaureenrogers
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox