Dijkstra's Quotes Considered Harmful
Charlie-Boo
With his EXIT from the subroutine of life, there is renewed interest
in the pearls of wisdom of Edsger Dijkstra. While I have always found
his writing colorful and entertaining, I have always believed that it
is a mistake to take his principles literally. I demonstrate with a
couple of examples:
1. "Program testing can best show the presence of errors but never
their absence".
Program testing does show that a particular input produces an
erroneous output. However, if the number of possible inputs is
reasonably small, then we can try all of them (manually or automated -
I often do the latter), and in fact show that a particular piece of
code is without error. Since most systems have a limited amount of
space for each input (and in general, since it is in fact a finite
state machine), then number of inputs is generally at least finite,
and often tenable.
2. "Restrict the use of the go to statement to alarm exits."
This is an oft quoted principle, that it is ok to use GOTO if you are
within a series of loops or subroutines, some sort of error is
detected, and the language allows you to terminate all of them in one
step.
I have never found this to be wise. The reason is, you should be
prepared to "clean up" each level above you, rather than aborting the
whole process. Even if you need to stop the whole process, loops or
subroutines above you may have files open, or need to send a message
to an operator that a particular step in the process has reached an
error, etc.
I generally pass back a value that tells each level above me if an
error occurs, so that they can each finish their business, then exit
up to the next level. Even if there is nothing to do at some
particular level, the logic/flow should be coded just in case (heaven
forbid) someone might want to change the code and add such a clean up
process before leaving the subroutine.
Agree or disagree?
Charlie Volkstorf
Cambridge, MA
http://www.mathpreprints.com/math/Preprint/CharlieVolkstorf/20021008.1/1
http://www.arxiv.org/html/cs.lo/0003071
David C. Ullrich
>Hello all,
>
>With his EXIT from the subroutine of life, there is renewed interest
>in the pearls of wisdom of Edsger Dijkstra. While I have always found
>his writing colorful and entertaining, I have always believed that it
>is a mistake to take his principles literally. I demonstrate with a
>couple of examples:
>
>1. "Program testing can best show the presence of errors but never
>their absence".
>
>Program testing does show that a particular input produces an
>erroneous output. However, if the number of possible inputs is
>reasonably small, then we can try all of them (manually or automated -
>I often do the latter), and in fact show that a particular piece of
>code is without error. Since most systems have a limited amount of
>space for each input (and in general, since it is in fact a finite
>state machine), then number of inputs is generally at least finite,
>and often tenable.
>
>2. "Restrict the use of the go to statement to alarm exits."
He didn't know about exceptions.
>This is an oft quoted principle, that it is ok to use GOTO if you are
>within a series of loops or subroutines, some sort of error is
>detected, and the language allows you to terminate all of them in one
>step.
>
>I have never found this to be wise. The reason is, you should be
>prepared to "clean up" each level above you, rather than aborting the
>whole process. Even if you need to stop the whole process, loops or
>subroutines above you may have files open, or need to send a message
>to an operator that a particular step in the process has reached an
>error, etc.
>
>I generally pass back a value that tells each level above me if an
>error occurs,
Oh - neither do you.
What does this have to do with sci.logic, btw?
> so that they can each finish their business, then exit
>up to the next level. Even if there is nothing to do at some
>particular level, the logic/flow should be coded just in case (heaven
>forbid) someone might want to change the code and add such a clean up
>process before leaving the subroutine.
>
>Agree or disagree?
>
>Charlie Volkstorf
>Cambridge, MA
>http://www.mathpreprints.com/math/Preprint/CharlieVolkstorf/20021008.1/1
>http://www.arxiv.org/html/cs.lo/0003071
David C. Ullrich
A N Neil
> Agree or disagree?
I disagree that your post is on math.
Dik T. Winter
> 1. "Program testing can best show the presence of errors but never
> their absence".
>
> Program testing does show that a particular input produces an
> erroneous output. However, if the number of possible inputs is
> reasonably small, then we can try all of them (manually or automated -
> I often do the latter), and in fact show that a particular piece of
> code is without error. Since most systems have a limited amount of
> space for each input (and in general, since it is in fact a finite
> state machine), then number of inputs is generally at least finite,
> and often tenable.
Most often the number of different inputs is finite but unmanageble.
> 2. "Restrict the use of the go to statement to alarm exits."
>
> This is an oft quoted principle, that it is ok to use GOTO if you are
> within a series of loops or subroutines, some sort of error is
> detected, and the language allows you to terminate all of them in one
> step.
>
> I have never found this to be wise.
You read it wrong. The principle states that the use of the go to
statement is *only* allowed for alarm exits. It does *not* say
that you should use a go to for an alarm exit. There are indeed
plenty situations where it is wise and can be done without problem.
Note that in his context a go to is also a return statement not at
the end of a subroutine, or an exit statement.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Jeremy Henty
Charlie-Boo wrote:
> Program testing does show that a particular input produces an
> erroneous output. However, if the number of possible inputs is
> reasonably small, then we can try all of them (manually or automated
> - I often do the latter), and in fact show that a particular piece
> of code is without error.
Not true! What if the code calls malloc() without checking whether
the return value is NULL? You could verify every possible input and
still see the program crash when memory is low.
BTW, I applaud you for taking the trouble to automatically verify the
behaviour of programs for all possible inputs. I wish even 1% of
software engineers did the same. But it does *not* prove correctness.
Regards,
Jeremy Henty
Sean
"Charlie-Boo" <ch...@aol.com> wrote in message
news:3df1e59f.02111...@posting.google.com...
> Hello all,
>
> With his EXIT from the subroutine of life, there is renewed interest
> in the pearls of wisdom of Edsger Dijkstra. While I have always found
> his writing colorful and entertaining, I have always believed that it
> is a mistake to take his principles literally. I demonstrate with a
> couple of examples:
>
> 1. "Program testing can best show the presence of errors but never
> their absence".
>
> Program testing does show that a particular input produces an
> erroneous output. However, if the number of possible inputs is
> reasonably small, then we can try all of them (manually or automated -
> I often do the latter), and in fact show that a particular piece of
> code is without error. Since most systems have a limited amount of
> space for each input (and in general, since it is in fact a finite
> state machine), then number of inputs is generally at least finite,
> and often tenable.
And what if your test battery contained an error. Or your
tester screwed up. There could have been a bug in your exhaustive
testing and now you think your code is perfect because it passed
that testing.
It is a very true statement.
>
> 2. "Restrict the use of the go to statement to alarm exits."
Disagree. If the code works and is readable, then screw how it
was coded, sell the thing.
enjoy,
Sean
David Wagner
>Program testing does show that a particular input produces an
>erroneous output. However, if the number of possible inputs is
This case is more the exception than the norm, in my experience.
Charlie-Boo
Then one of the inputs to the subroutine is the amount of space available!
Charlie
Carlos Felippa
> Hello all,
>
> With his EXIT from the subroutine of life, there is renewed interest
> in the pearls of wisdom of Edsger Dijkstra. While I have always found
> his writing colorful and entertaining, I have always believed that it
> is a mistake to take his principles literally. I demonstrate with a
> couple of examples:
>
> 1. "Program testing can best show the presence of errors but never
> their absence".
>
> Program testing does show that a particular input produces an
> erroneous output. However, if the number of possible inputs is
> reasonably small, then we can try all of them (manually or automated -
> I often do the latter), and in fact show that a particular piece of
> code is without error. Since most systems have a limited amount of
> space for each input (and in general, since it is in fact a finite
> state machine), then number of inputs is generally at least finite,
> and often tenable.
Just imagine testing the 64-bit multiply Z = X*Y for all X,Y.
Both X and Y can have 2^64 values, so you need
2^128 tests. At 2^15 tests per sec, that will take
10^110 years. And that is a simple program ...
(This example is in fact due to EWD, Notes on Structured Programming,
Acedemic Press, p.4, except that the machine words therein were 27-bit)
The idea of Don Knuth for TeX and MetaFont has more sense: test
systematically for "perverse" inputs, for example \hsize=0pt in TeX.
Michael J. Fromberger
ch...@aol.com (Charlie-Boo) wrote:
> Edsger Dijkstra. While I have always found his writing colorful and
> entertaining, I have always believed that it is a mistake to take his
> principles literally. I demonstrate with a couple of examples:
>
> 1. "Program testing can best show the presence of errors but never
> their absence".
>
> Program testing does show that a particular input produces an
> erroneous output. However, if the number of possible inputs is
> reasonably small, then we can try all of them (manually or automated
> - I often do the latter)
In my experience, there are very few "interesting" programs whose input
set is actually small enough that you can, in practise, exhaustively
test all possible inputs. Remember, of course, that any program which
reads user input, opens and reads a file, or runs in an environment in
which it can be interrupted by signals or in which system calls may
fail, has far more input than just the "formal parameters" its primary
function might take.
For instance, even if you can test your program with all its possible
input values (in the narrower sense of "input parameters"), how do you
know that its successful completion given those values could not be made
wrong if, by some coincidence, a system call your program relies upon
returns an error which your program ignores (and therefore your program
does not compensate for it and winds up giving incorrect output). Such
a program would be, in a very real sense, "wrong", and yet it might
produce correct outputs for all of the "possible input" values, by
simple good fortune!
So, I would argue that Dijkstra was still right, in this matter.
> 2. "Restrict the use of the go to statement to alarm exits."
>
I think if we ended the sentence after the word "statement", it would be
a better and more general principle. It's not that GOTO can never be
used correctly or responsible; merely that its use should be considered
very carefully by the programmer, and the presence of a GOTO in a
program ought to appeal to some justification.
Cheers,
-M
--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA
Jeremy Henty
Charlie-Boo wrote:
> Jeremy Henty <jer...@chaos.org.uk> wrote in message
> news:<slrnataf5o...@ganglion.demon.co.uk>...
>
>> In article <3df1e59f.02111...@posting.google.com>,
>> Charlie-Boo wrote:
>>
>> > However, if the number of possible inputs is reasonably small,
>> > then we can try all of them (manually or automated - I often do
>> > the latter), and in fact show that a particular piece of code is
>> > without error.
>>
>> Not true! What if the code calls malloc() without checking whether
>> the return value is NULL? You could verify every possible input
>> and still see the program crash when memory is low.
>
> Then one of the inputs to the subroutine is the amount of space
> available!
This answer simply concedes that Dikstra is effectively right. The
number of possible values of "amount of space available" is in no way
"reasonably small". And we haven't even begun to consider all the
other ways that the code could interact with the operating system.
Regards,
Jeremy Henty
jmfb...@aol.com
David C. Ullrich <ull...@math.okstate.edu> wrote:
>On 15 Nov 2002 07:10:54 -0800, ch...@aol.com (Charlie-Boo) wrote:
>
>>Hello all,
>>
>>With his EXIT from the subroutine of life, there is renewed interest
>>in the pearls of wisdom of Edsger Dijkstra. While I have always found
>>his writing colorful and entertaining, I have always believed that it
>>is a mistake to take his principles literally. I demonstrate with a
>>couple of examples:
>>
>>1. "Program testing can best show the presence of errors but never
>>their absence".
>>
>>Program testing does show that a particular input produces an
>>erroneous output. However, if the number of possible inputs is
>>reasonably small, then we can try all of them (manually or automated -
>>I often do the latter), and in fact show that a particular piece of
>>code is without error. Since most systems have a limited amount of
>>space for each input (and in general, since it is in fact a finite
>>state machine), then number of inputs is generally at least finite,
>>and often tenable.
[emoticon talking out of prefix] You are wrong. There is no way
to positively verify all future executions of a program.
>>
>>2. "Restrict the use of the go to statement to alarm exits."
>
>He didn't know about exceptions.
He was also _not_ talking about interrupt handlers or operating
systems. I don't understand why people keep taking this so-called
quote out of context.
<snip>
/BAH
Subtract a hundred and four for e-mail.
jmfb...@aol.com
It doesn't matter if there is even one datum. You cannot verify
future successful executions of the code. All you can do is
show that the code can handle the datum under controlled conditions.
The poster who started this thread isn't paranoid enough :-).
Nico Benschop
>
> Hello all,
>
> With his EXIT from the subroutine of life, there is renewed interest
> in the pearls of wisdom of Edsger Dijkstra. While I have always found
> his writing colorful and entertaining, I have always believed that it
> is a mistake to take his principles literally. I demonstrate with a
> couple of examples:
>
> 1. "Program testing can best show the presence of errors but never
> their absence".
>
> Program testing does show that a particular input produces an
> erroneous output. However, if the number of possible inputs is
> reasonably small, then we can try all of them (manually or automated -
> I often do the latter), and in fact show that a particular piece of
> code is without error. Since most systems have a limited amount of
> space for each input (and in general, since it is in fact a finite
> state machine), then number of inputs is generally at least finite,
> and often tenable.
It is not the number of inputs (as variables), but the total input space
they span (re 'direct product' of the input variable sets). Which can
(an usually is) be huge, for present-day computers /systems, even if
the # input variables is small. So your example is an extreme exception.
> 2. "Restrict the use of the go to statement to alarm exits."
>
> This is an oft quoted principle, that it is ok to use GOTO if you
> are within a series of loops or subroutines, some sort of error is
> detected, and the language allows you to terminate all of them in
> one step. [...] -- Charlie Volkstorf
You should know the motivation /context this rule comes from.
Dijkstra's effort was, as I understand it (and I knew him personally),
to improve and propagate the concepts and practice of 'structured
programming' - as answer to the (in the 70's) rampant chaos in software
production. GOTO's were popular since the early FORTRAN times of
programming - but they, if indiscriminately used, often destroyed
program structure (re: a network of subroutines without 'side effects')
that may have been originally intended. So his advice was: avoid GOTO's
as the plague (he referred to GOTO-infested programs as 'spaghetti'
;-)
-- NB:
http://www.mathpreprints.com/math/Preprint/n.f.benschop/show/Author/
jmfb...@aol.com
Unfortunately, instructors interpreted his common sense as a
golden commandment and began to teach the extreme. We're still
suffering from that today and it's been 30 years!
Taneli Huuskonen
Hash: SHA1
In <6bd3575.02111...@posting.google.com>
car...@colorado.edu (Carlos Felippa) writes:
[...]
>Just imagine testing the 64-bit multiply Z = X*Y for all X,Y.
>Both X and Y can have 2^64 values, so you need
>2^128 tests. At 2^15 tests per sec, that will take
>10^110 years. And that is a simple program ...
Performing 2^128 tests at 2^15 tests per second (a very modest testing
rate, BTW) would take "only" 2^113 seconds or about 3.3 x 10^26 years.
Of course, the testing is impossible in practice anyway.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPde7+l+t0CYLfLaVEQKbFwCgyP+K7aWZA3x2+xj3vW5PwECvvV0An0kl
3huG+u67wjbz0xS9i9TAGogI
=jn38
-----END PGP SIGNATURE-----
--
I don't | All messages will be PGP signed, | The ultimate large
speak for | encrypted mail preferred. Keys: | cardinal: it's so large
the Uni. | http://www.helsinki.fi/~huuskone/ | it isn't true.
Carlos Felippa
>
> Performing 2^128 tests at 2^15 tests per second (a very modest testing
> rate, BTW) would take "only" 2^113 seconds or about 3.3 x 10^26 years.
> Of course, the testing is impossible in practice anyway.
>
2^88 = 10^85 years. A long time anyway since according to the latest BB
data the age of the universe is 14 10^9 years, give or take a few.
I always enjoyed EWD's no-holds-barred comments. Some that evolved from
his ACM Turing lecture, re languages of the time (mid 1970s):
FORTRAN --"the infantile disorder"--, by now nearly 20 years old,
is hopelessly inadequate for whatever computer application you have
in mind today: it is now too clumsy, too risky, and too expensive to use.
PL/I --"the fatal disease"-- belongs more to the problem set than
to the solution set.
It is practically impossible to teach good programming to students that
have had a prior exposure to BASIC: as potential programmers they are
mentally mutilated beyond hope of regeneration.
The use of COBOL cripples the mind; its teaching should, therefore,
be regarded as a criminal offence.
APL is a mistake, carried through to perfection. It is the language of
the future for the programming techniques of the past: it creates a
new generation of coding bums.
Imagine what he would have to say about C++, Java or C# !
Heikki Kaskelma
> 2^88 = 10^85 years.
You have either big twos or small tens.
Heikki Kaskelma
Dik T. Winter
...
> (This example is in fact due to EWD, Notes on Structured Programming,
> Acedemic Press, p.4, except that the machine words therein were 27-bit)
Yup, the Electrologica X1 and X8, where the maximal integer is
67108863 (which for some reason I still know from memory).
Ms O. Philia
<snip> I have never found this to be wise. <snip>
>I generally pass back a value that tells each level above me if an
> error occurs, so that they can each finish their business, then exit
> up to the next level. Even if there is nothing to do at some
> particular level, the logic/flow should be coded just in case (heaven
> forbid) someone might want to change the code and add such a clean up
> process before leaving the subroutine.
>
> Agree or disagree?
Well, ...
"Charlie-Boo" <ch...@aol.com> wrote in message
news:3df1e59f.02102...@posting.google.com...( Re: Gregory
Chaitin's Omega is Not Well Defined (again))<snip> the following program P:
>
> 1. Read in nonnegative integer N
> 2. If N=2 then Halt
> 3. Initialize scratch value X equal to 3
> 4. If N<X then Loop
> 5. Double X
> 6. If N<X then Halt
> 7. Double X
> 8. Go to step 4
<snip> (Note that he never responds to flaws in his work.)
The flaw here may stem from a confusion between God and Santa Claus as
mutually exclusive members of the set of examples which can't be produced?
This is only brought up because in an earlier discussion on sci.logic and
comp.ai.philosophy concerning claims by the philosopher David J. Chalmers
who evinces similar confusion in his paper, "On Sense and Intension" with
his unfortunate choice of a term with no extension, "For example, some terms
(e.g. 'Santa Claus') appear to have no referent: in such a case, one might
say that they lack extension, or one might say that they have a null
extension." Charlie Boo said, "I'm Santa Claus or this is false."
Hmm... Gotta take a bath. ;-)
Charlie-Boo
> >>
> >> > However, if the number of possible inputs is reasonably small,
> >> > then we can try all of them (manually or automated - I often do
> >> > the latter), and in fact show that a particular piece of code is
> >> > without error.
> >>
> >> Not true! What if the code calls malloc() without checking whether
> >> the return value is NULL? You could verify every possible input
> >> and still see the program crash when memory is low.
> >
> > Then one of the inputs to the subroutine is the amount of space
> > available!
>
> This answer simply concedes that Dikstra is effectively right. The
> number of possible values of "amount of space available" is in no way
> "reasonably small". And we haven't even begun to consider all the
> other ways that the code could interact with the operating system.
>
> Regards,
>
> Jeremy Henty
To show one example of a program for which it is not practical to try
all possible inputs doesn't prove anything. (I am not so sure that
you even did that, but it is not hard to do.) The point is that
Dijkstra said that debugging never proves that a propgram is correct,
and that is not true. It sometimes does.
I didn't say that every program can be proven correct. My Gawd. We
all know that we can't decide squat about EVERY program.
Michael J. Fromberger
I would actually turn this around, and say that the fact we may be able
to demonstrate a program which CAN be shown correct this way (which
hasn't been done here, as yet) does not invalidate Dr. Dijkstra's basic
point. As I read it, his statement is more of a strong generalization
about testing, than a mathematical theorem about correctness.
Experience bears out his claim: "Testing," for almost any non-trivial
program, does not imply "exhaustive testing." Rather, it implies some
kind of focussed sampling technique, where you pick some (hopefully
diverse) set of inputs, and verify that the program does what it's
supposed to when given those inputs. If the program fails on such
inputs, it's clearly wrong; but the fact that it passes says very little
about the program's correctness.
I don't think his claim is at all unreasonable. In fact, as a thought
exercise, suppose I've written a program P, and I want to prove to you
that it's correct. You choose some input values: x, y, and z. I run P
on them to obtain x' = P(x), y' = P(y), and z' = P(z). For the sake of
argument, suppose P(x) is wrong. So you say, "Michael, your program is
wrong! The value of P(x) should be q, not x'."
Apologizing profusely, I tell you I'll fix the problem right away. So I
write a new program P', which behaves as follows:
P'(input) is:
if the input is x, then
return q
otherwise,
run P(input) and return its value.
Obviously, P' is equivalent to P for all input values besides x, and it
gives the correct answer for x, which P did not. Is P correct? Give me
some more test values. We can go back and forth like this all day long,
until (in the worst case) I've got nothing but a big set of conditionals
for every input you've ever bothered to test. That certainly proves
that P isn't correct on its own, but it doesn't mean my new program IS
correct.
If you are only allowed to test the program in this way -- by supplying
inputs and comparing the outputs to known-good values -- write a program
that will fool you, and might still be wrong. The implication of Dr.
Dijkstra's comment, I think, is that the only way for you to truly be
convinced that my program works is if I give you the code along with a
proof that the code has got to work, based on its structure, rather than
its behaviour. For "interesting" programs, you won't be able to test
all the possible cases in a reasonable amount of time.
David Wagner
>The point is that
>Dijkstra said that debugging never proves that a propgram is correct,
>and that is not true. It sometimes does.
Sure, of course. But such programs are probably exceptionally rare
in practice. To focus on the rare counterexamples would be to miss the
essential insight behind Dijkstra's quote.
Sometimes a little bit of hyperbole makes for more effective and efficient
communication for all involved, so long as we agree not to quibble over
minor inessential details.
G. Frege
<Michael.J....@Clothing.Dartmouth.EDU> wrote something quite
reasonable.
Michael you shouldn't bother to much. This guy is a well know Usenet
troll. (Try to find other threads he started...)
Actually he is claiming nonsense most of the times. (Last time he
proved the _real_ existence of a self-containing set, etc.)
>
> I would actually turn this around, and say that the fact we may be able
> to demonstrate a program which CAN be shown correct this way (which
> hasn't been done here, as yet) does not invalidate Dr. Dijkstra's basic
> point.
>
Actually we CAN'T show a program to be correct ONLY by testing!
I short _proof_ for that claim: You have two programs A and B. You are
given the following information: The programs should do the following:
Taking a integer number from the set {1, 2, 3} as input and
print out the same number again.
Well, so let's test the programs. And let's assume we get the
following results:
A: (Input, Output): (1,1), (2,2), (3,3)
B: (Input, Output): (1,1), (2,2), (3,3)
Wow. Great! Obviously they are correct. No?
Actually WE STILL DON'T KNOW. And we even down know after as much TEST
CASES as we want!
Suppose that A has the following CODE:
0: wait for input
1: write input into var
2: print var
3: goto 0.
And B:
0: wait for input
1: allocate new storage for var
2: write input into var
3: print var
4: goto 0.
Actually A is correct (as we can see by looking at its CODE) but B is
not: since the amount of storage is _finite_. Sooner or later it will
stop functioning correctly.
But HOW will you be able to KNOW THAT just by looking at the
*behavior* of the programs for finitely many test cases? (How do you
know when you can STOP _testing_?! Without KNOWING and actually
UNDERSTANDING the CODE?!)
And how will you be able determine JUST BY TESTING that there's
something wrong with program C:
0: wait for input
1: write input into var
2: if date >= 1.1.2005 have fun
3: print var
4: goto 0.
Actually you may test AS MUCH AS YOU want, you won't find a "bug" ...
until the program stops to work correctly ("all of a sudden").
Or program D:
0: n = 0.
1: wait for input
2: write input into var
3: n := n+1
4: if n > 10000000 EXIT
5: print var
6: goto 1.
etc.
Concerning D: For any number N of tests to be performed, I can always
give you a program D' that will pass ALL that tests, and still be
faultily; it will fail for, say, number of tests > 2*N.
With other words: for ANY possible test (procedure) that can be
performed there might always be a program that will pass all the tests
and still be faultily. Hence "program testing can best show the
presence of errors but never their absence".
-----------------------
Actually Dijkstra's is _completely_ correct. NO need to "weaken" it.
>
> Experience bears out his claim: "Testing," for almost any non-trivial
> program, does not imply "exhaustive testing."
>
You see, if "exhaustive testing" in the sense -ALL possible input
values are supplied and the output is checked- does not show (prove)
that the code actually is correct. (That it will work in the assumed
way for ANY input value you deliver - even if it's from the set of all
POSSIBLE input values.)
But still your comments are correct, if considered real testing
scenarios.
> ...it implies some
> kind of focussed sampling technique, where you pick some (hopefully
> diverse) set of inputs, and verify that the program does what it's
> supposed to when given those inputs. If the program fails on such
> inputs, it's clearly wrong; but the fact that it passes says very little
> about the program's correctness.
>
See proof above.
>
> If you are only allowed to test the program in this way -- by supplying
> inputs and comparing the outputs to known-good values -- write a program
> that will fool you, and might still be wrong.
>
:-) Exactly.
By the way, what you describe IS what usually is meant with the term
"testing". And CLEARLY that is what Dijkstra's refereed to. (*sigh*)
>
> The implication of Dr.
> Dijkstra's comment, I think, is that the only way for you to truly be
> convinced that my program works is if I give you the code along with a
> proof that the code has got to work, based on its structure, rather than
> its behaviour [alone].
>
Exactly!
Moreover:
>
> For "interesting" programs, you won't be able to test
> all the possible cases in a reasonable amount of time.
>
Yeah, but even if you COULD (see examples above) NOTHING WOULD BE
ENSURED in this way.
*Sigh*
If Charlie-Boo (sic!) were a serious person I would suggest that he
should read something about _proof by (empirical) induction_; it's
well known that this is NOT strong enough to ensure anything.
F.
6.363
The procedure of induction consists in accepting as true the simplest
law that can be reconciled with our experiences.
6.3631
This procedure, however, has no logical justification but only a
psychological one. It is clear that there are no grounds for believing
that the simplest eventuality will in fact be realized.
6.36311
It is an hypothesis that the sun will rise tomorrow: and this means
that we do not k n o w whether it will rise.
6.37
There is no compulsion making one thing happen because another has
happened. The only necessity that exists is logical necessity.
G. Frege
>
> Program testing does show that a particular input produces an
> erroneous output. However, if the number of possible inputs is
> reasonably small, then we can try all of them (manually or automated -
> I often do the latter), and in fact show that a particular piece of
> code is without error.
>
Nonsense.
Assume you have to test a program A, that should exhibit the
following behavior:
Input data: a value from the set {1, 2, 3}
Output data: x if input is x.
Now I would think that the "number of possible inputs is reasonably
small"; won't you think so?
Hence we can "try all of them".
Now assume we have got the following results:
(input, output): (1,1)(2,2)(3,3)(2,2)(2,2)(1,1) ... etc.
Actually only finite many tests can be performed in finite time. :-)
Now let's say we have performed N tests.
Now would this really show "that [the following] particular piece of
code is without error"?
0: n = 0.
1: wait for input
2: write input into var
3: n := n+1
4: if n > 2*N EXIT
5: print var
6: goto 1.
Actually the code WOULD pass our test. BUT still be erroneous. It
would stop to work correctly if we perform more than 2*N input-output
cycles.
F.
Or how about:
0: wait for input
1: write input into var
2: if date >= 1.1.2005 have fun
3: print var
4: goto 0.
Probably you remember the problems with: >= 1.1.2000 (?)
Or:
0: wait for input
1: allocate new storage for var
2: write input into var
3: print var
4: goto 0.
PLEASE NOTE that it's NOT THE CASE THAT "one of the inputs to the
subroutine is the amount of space available!"
First of all, we didn't talk about "subroutines" but about
programs!
Actually the correct behavior of the program _depends_ on the amount
of space available! But it's NOT a value ***you*** may supply as an
"input" or not. (It depends on the actual system state! BTW, NOT
freeing allocated memory after usage IS a common program bug, usually
refereed to as memory hole.)
------------------------------------------------------
Well, your comments would make MORE sense if you would talk about
"parameters" that are connected with performing a certain program. Of
course this "parameters" can be checked too while performing tests.
And ONE of this parameters certainly would be memory. (Hence one could
SEE if there actually is a memory hole.) On the other hand, we
wouldn't _see_ the condition: date >= 1.1.2005 (for example). Yes of
course: system date and time is _another_ parameter (that's influence
on the program ALSO could be considered), etc.
All this parameters form the _context_ of program execution. And
actually they extend the space of "possible machine states" to be
checked/tested in a way that does not allow any more for an
_exhaustive test_ (for all possible parameters AND input data).
Finally, even if we could do THAT, we still would not catch the bug:
if n > 2*N EXIT.
To detect this type of bug [before actually facing it] we HAVE TO know
(and check) the CODE!
Do you NOW _understand_ the meaning of:
G. Frege
>
> Dijkstra said that debugging never proves that a program is correct,
> and that is not true. It sometimes does.
>
Actually he DIDN'T say "debugging never proves that a program is
correct" but "Program testing can best show the presence of errors but
never their absence". That's a _certain_ difference!
At the process of _debugging_ you are investigating the CODE _and_
it's behavior; actually this is some sort of program ANALYSIS.
_Testing_ is something completely different! *sigh*
F.
jmfb...@aol.com
>> >>
>> >> > However, if the number of possible inputs is reasonably small,
>> >> > then we can try all of them (manually or automated - I often do
>> >> > the latter), and in fact show that a particular piece of code is
>> >> > without error.
>> >>
>> >> Not true! What if the code calls malloc() without checking whether
>> >> the return value is NULL? You could verify every possible input
>> >> and still see the program crash when memory is low.
>> >
>> > Then one of the inputs to the subroutine is the amount of space
>> > available!
>>
>> This answer simply concedes that Dikstra is effectively right. The
>> number of possible values of "amount of space available" is in no way
>> "reasonably small". And we haven't even begun to consider all the
>> other ways that the code could interact with the operating system.
>>
>> Regards,
>>
>> Jeremy Henty
>
>To show one example of a program for which it is not practical to try
>all possible inputs doesn't prove anything. (I am not so sure that
>you even did that, but it is not hard to do.) The point is that
>Dijkstra said that debugging never proves that a propgram is correct,
>and that is not true. It sometimes does.
No, it doesn't. Perhaps you don't understand what debugging is?
>
>I didn't say that every program can be proven correct. My Gawd. We
>all know that we can't decide squat about EVERY program.
You can't decide squat with one program.
jmfb...@aol.com
<Michael.J.Fromberger-...@merrimack.dartmouth.edu>,
"Michael J. Fromberger" <Michael.J....@Clothing.Dartmouth.EDU>
wrote:
Our assembler would report "No errors detected" after
a successful assembly. Seeing that message print across
the paper always caused JMF to chuckle.
<snip exercise>
jmfb...@aol.com
G. Frege <in...@simple-line.de> wrote:
>On Tue, 19 Nov 2002 01:45:15 -0500, "Michael J. Fromberger"
><Michael.J....@Clothing.Dartmouth.EDU> wrote something quite
>reasonable.
>
>Michael you shouldn't bother to much. This guy is a well know Usenet
>troll. (Try to find other threads he started...)
>
>Actually he is claiming nonsense most of the times. (Last time he
>proved the _real_ existence of a self-containing set, etc.)
>
>>
>> I would actually turn this around, and say that the fact we may be able
>> to demonstrate a program which CAN be shown correct this way (which
>> hasn't been done here, as yet) does not invalidate Dr. Dijkstra's basic
>> point.
>>
>Actually we CAN'T show a program to be correct ONLY by testing!
I can cause any program to not work. Hint: pull the plug.
There is no such thing as a faultless program...unless you
count the ones that are never executed.
jmfb...@aol.com
Good for you! You stated it much better than I did. I am certainly
appalled that somebody doesn't know what debugging is or its
purpose and is citing Dijkstra to teach that ignorance.
Taneli Huuskonen
Hash: SHA1
In <6bd3575.02111...@posting.google.com> car...@colorado.edu
(Carlos Felippa) writes:
>2^88 = 10^85
(I don't think I'm misrepresenting you by selective quotation, but
please let me know if you disagree.)
Actually, 2^88 = 309485009821345068724781056, or approximately
3.1 x 10^26.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPdpl9F+t0CYLfLaVEQJkUQCgqmjJbozzTjlePCI4w/n3Uj+amXYAnAzh
nMRDdStUqSHBE/K60vZzxps6
=Sjmt
Charlie-Boo
wrote in
> The fact we may be able
> to demonstrate a program which CAN be shown correct this way (which
> hasn't been done here, as yet) does not invalidate Dr. Dijkstra's basic
> point. As I read it, his statement is more of a strong generalization
> about testing, than a mathematical theorem about correctness.
He said that you can't prove it correct by testing it, which is wrong.
He didn't consider automated testing of all possible inputs. He's
just not that smart, that's all. He became famous by writing a letter
to the editor of CACM saying that spaghetti code is hard to maintain,
and spent the rest of his life talking about it.
>
> Experience bears out his claim: "Testing," for almost any non-trivial
> program, does not imply "exhaustive testing."
No, but it allows it. Exhaustive testing is a special case of
testing. And automated exhaustive testing is a special case of that.
Dijkstra talked endlessly about systematic programming, but never
provided a system for programming. He just threw around a bunch of
colorful terms. If you want to lap it up, that's your mistake.
> We can go back and forth like this all day long,
> until (in the worst case) I've got nothing but a big set of conditionals
> for every input you've ever bothered to test. That certainly proves
> that P isn't correct on its own, but it doesn't mean my new program IS
> correct.
# 1. You do all of the testing in one sitting. You don't do some at a
time.
# 2. If you kludge it up for every possible input value, then it IS
correct. Who says a program can't be one big CASE statement?
> For "interesting" programs, you won't be able to test
> all the possible cases in a reasonable amount of time.
I write applications for hospitals and I do it all the time. Mr.
Dijkstra and yourself seem to have forgotten that in the REAL WORLD
lots of things are finite. I routinely test date and time utilities
exhaustively.
Consider the following algorithm: You have a list of time intervals
assumed to occur within one day. The problem is to determine the
maximum number of intervals that overlap at any point in time. There
is a very inefficient algorithm for determining this, and there is a
tricky, efficient one. Using the inefficient algorithm to check the
correctness of the efficient one, I ran automated tests and uncovered
a number of bugs in the efficient algorithm. Dijkstra never talked
about practical techniques like this.
> -M
Charlie Volkstorf
Cambridge, MA
G. Frege
>
> He said that you can't prove it correct by testing it, which is wrong.
>
Even if you repeat it 1000 times, idiot, it will still be wrong.
>
> He didn't consider automated testing of all possible inputs.
>
He didn't consider the possibility that brainless idiots might comment
his sayings.
> He's just not that smart, that's all.
>
< No comment. >
> He became famous by writing a letter to the editor of CACM
> saying that spaghetti code is hard to maintain, and spent the
> rest of his life talking about it.
>
??? I guess something is wrong with your medication again, Charlie.
>
> Dijkstra talked endlessly about systematic programming
> provided a system for programming. He just threw around
> a bunch of colorful terms.
>
Are you on drugs, or what?!
>
> I write applications for hospitals and I do it all the time.
>
Well, at least it's clear now where you got your stuff from... :-)
> Mr. Dijkstra and yourself seem to have forgotten that in the REAL WORLD
> lots of things are finite.
>
Yeah. For example the volume of your brain.
>
> Consider the following algorithm: You have a list of time intervals
> assumed to occur within one day. The problem is to determine the
> maximum number of intervals that overlap at any point in time. There
> is a very inefficient algorithm for determining this, and there is a
> tricky, efficient one. Using the inefficient algorithm to check the
> correctness of the efficient one, I ran automated tests and uncovered
> a number of bugs in the efficient algorithm.
>
So what...?
>
> Dijkstra never talked about practical techniques like this.
>
I SERIOUSLY doubt that you have the SLIGHTEST idea about which topics
Dijkstra d i d or didn't talk...
*sigh*
F.
Actually I find it quite depressing, that morons like you dare to talk
in this silly and brainless way about one of the greatest computer
scientists ("Informatiker") of the 20th century. :-(
G. Frege
>
> Note that he never responds to flaws in his work.
>
Yes, obviously he's just a silly asshole who likes to troll around.
Actually people of that kind are a real pest.
F.
Alfred Einstead
> Actually we CAN'T show a program to be correct ONLY by testing!
You can, if by a systematic analysis of the program's structure,
you know that the data set used to test the program with is
representative in the following sense:
(A) The program works correctly if it works correctly on
all the data in the set.
(B) The program works incorrectly if it works incorrectly
on at least one data item in the set.
This would be a set of "eigendata" for the program.
> I short _proof_ for that claim: You have two programs A and B. You are
> given the following information: The programs should do the following:
> Taking a integer number from the set {1, 2, 3} as input and
> print out the same number again.
> Well, so let's test the programs. And let's assume we get the
> following results:
> A: (Input, Output): (1,1), (2,2), (3,3)
> B: (Input, Output): (1,1), (2,2), (3,3)
> Wow. Great! Obviously they are correct. No?
This is not relevant since nothing in the passage above
indicates whether {1,2,3} is an eigendata set for either A or B.
The relevant conditions and criteria would be this. Suppose you
have a program P to implement an algorithm A for a function f: N -> N.
Suppose that, by an analysis of the internal structure of A (and P),
you find that N0(P,A) is a finite subset of N with the property that
P computes f(n) with input n, for all n in N
if and only if
P computes f(n) with input n, for all n in N0(P,A).
Then testing P with any subset of N containing N0(P,A) will be
sufficient to prove that A computes the given function f(n).
Ultimately, since physical machines are finite state machines,
the existence of eigendata sets arises as a result of the
Pumping Lemma for finite state machines.
Alfred Einstead
> 6.363
> The procedure of induction consists in accepting as true the simplest
> law that can be reconciled with our experiences.
>
> 6.3631
> This procedure, however, has no logical justification but only a
> psychological one.
That's clearly wrong. In fact, it's a standard result of proof
theory that if a statement involving a specific data item is
proven and if no essential use is made of any properties of
that item then the statement holds for ALL items, and not
just the specific one. The item in question is generally
referred to as an "eigendatum" of the statement in question.
Corollary 24G:
Asssume that G |- phi(c), where the constant symbol c does not
occur in any of the hypotheses in G nor in phi(x). Then
G |- for all x: phi(x).
(Enderton, "An Introduction to Mathematical Logic", Academic
Press 1972).
> It is clear that there are no grounds for believing
> that the simplest eventuality will in fact be realized.
The author of this passage is not well-versed in proof theory
and needs to learn his or her logic.
> 6.36311
> It is an hypothesis that the sun will rise tomorrow: and this means
> that we do not k n o w whether it will rise.
However, we DO know that IF all the relevant conditions that
pertained to the rising of the sun CONTINUE to pertain and that
if nothing of essence changes to the following day, then the
sun WILL continue to rise.
The only open issue is not *whether* the sun will rise or not,
but *whether* the conditions we observe to hold true are in fact
the essential conditions that dictate the continuing rising of
the sun.
> 6.37
> There is no compulsion making one thing happen because another has
> happened. The only necessity that exists is logical necessity.
The empirical assertion(s) that one has indeed captured the essential
conditions behind a given phenonemon DOES provide the necessary
compulsion. The desired conclusion then follows logically from
the empirical assertion(s) in question.
G. Frege
wrote:
> >
> > Actually we CAN'T show a program to be correct ONLY by testing!
> >
> You can, if by a systematic analysis of the program's structure,
> you know that the data set used to test the program with
> is representative in the following sense:
>
> (A) The program works correctly if it works correctly on
> all the data in the set.
> (B) The program works incorrectly if it works incorrectly
> on at least one data item in the set.
>
Yes, of course. ( You certainly noticed the word _only_ in the claim
above? )
Strange communication pattern you have:
I : We (man) can't fly ONLY by flapping with the arms.
You: You can, if using an airplane.
*sigh*
> >
> > Well, so let's test the programs. And let's assume we get the
> > following results:
> >
> > A: (Input, Output): (1,1), (2,2), (3,3)
> > B: (Input, Output): (1,1), (2,2), (3,3)
> >
> > Wow. Great! Obviously they are correct. No?
> >
> This is not relevant since nothing in the passage above
> indicates whether {1,2,3} is an eigendata set for either A or B.
>
Sure. But that does in no way invalidate the (original) argument.
You know we were talked about _testing_: supplying input data, and
checking the behavior of the program. Actually it should produce the
desired output for _any_ (instance of) input data.
Without knowing the internal structure of a program and an appropriate
program analysis no information concerning "eigendata" is available
(in general).
Hence testing ALONE usually won't suffice.
>
> The relevant conditions and criteria would be this. Suppose you
> have a program P to implement an algorithm A for a function f: N -> N.
> Suppose that, by an analysis of the internal structure of A (and P),
> you find that N0(P,A) is a finite subset of N with the property that
>
> P computes f(n) with input n, for all n in N
> if and only if
> P computes f(n) with input n, for all n in N0(P,A).
>
> Then testing P with any subset of N containing N0(P,A) will be
> sufficient to prove that A computes the given function f(n).
>
Well, in the program(s) mentioned in my former post _all_ P has to do
is "computing"
id(n) for input n from the set { 1, 2, 3 } and doing nothing
for any other (possible) input value.
And it seems that {1, 2, 3} u { some finite input data } *) are the
necessary eigendata-values, if the program has the form:
0: wait for input
1: write input into var
2: if var in {1, 2, 3 } print var
3: goto 0.
*) For example any possible "key press" action, if the program is
character based. (The input data is taken from keyboard only.)
Hmmm... Actually we will ASSUME that no keyboard action will
produce an error, and that ANY 'input' that is longer than
1 character is truncated to 1 effective "input" character.
On the other hand... what would the eigendata values have to be for a
program of the form?
0: wait for input
1: allocate new storage for var
2: write input into var
3: if var in {1, 2, 3 } print var
4: goto 0.
Or:
0: wait for input
1: write input into var
2: if date >= 1.1.2005 EXIT
3: if var in {1, 2, 3 } print var
4: goto 0.
Or:
0: n = 0.
1: wait for input
2: write input into var
3: n := n+1
4: if n > 10000000 EXIT
5: if var in {1, 2, 3 } print var
6: goto 1.
Obviously we have to _analyze_ the programs FIRST to determine the set
of "eigendata" (if it does exist).
F.
G. Frege
wrote:
> >
> > 6.363
> > The procedure of induction consists in accepting as true the simplest
> > law that can be reconciled with our experiences.
> >
> > 6.3631
> > This procedure, however, has no logical justification but only a
> > psychological one.
>
> That's clearly wrong.
>
Where does it hurt?!
MAN, we are talking about _empirical induction_ here. NOT about a
deductive system of logic. ***sigh***
>
> Asssume that G |- phi(c), where the constant symbol c does not
> occur in any of the hypotheses in G nor in phi(x). Then
>
> G |- for all x: phi(x).
>
> (Enderton, "An Introduction to Mathematical Logic", Academic
> Press 1972).
>
Actually you will find that principle already mentioned in
Begriffsschrift, 1879. :-)
"For example, we can instead of
|-------- X(c)
write
|---(x)--- X(x) ,
if c only occurs at the argument places in X(c)."
Note that there are no hypotheses in this system.
And:
"It's also obvious that from
|-------- A -> Phi(c)
it can be derived
|-------- A -> (x) Phi(x) ,
if A is an expression in which c does not occur, and if c only occurs
at the argument places in Phi(c)."
Yes, he actually uses the "letter" Phi here. :-)
> >
> > It is clear that there are no grounds for believing
> > that the simplest eventuality will in fact be realized.
> >
> The author of this passage is not well-versed in proof theory
> and needs to learn his or her logic.
>
Well, the author of this passage (Mr. L. Wittgenstein) is LONG, LONG
dead, and hence doesn't need to learn any logic any more. :-)
Actually it seems to be of more relevance concerning _your_ own
person. :-)
> >
> > 6.36311
> > It is an hypothesis that the sun will rise tomorrow: and this means
> > that we do not k n o w whether it will rise.
> >
> However, we DO know that IF all the relevant conditions that
> pertained to the rising of the sun CONTINUE to pertain and that
> if nothing of essence changes to the following day, then the
> sun WILL continue to rise.
>
1. But DO we k n o w that all the relevant conditions that
pertained to the rising of the sun _will_ CONTINUE?
2. You argument hinges on the validity of the "law of causality". How
do we actually KNOW that this "law" holds?
> >
> > 6.37
> > There is no compulsion making one thing happen because another has
> > happened. The only necessity that exists is logical necessity.
>
> The empirical assertion(s) that one has indeed captured the essential
> conditions behind a given phenomenon [ etc., etc. ]
>
You still don't understand. :-)
6.371
At the basis of the whole modern view of the world lies the illusion
that the so-called laws of nature are the explanations of natural
phenomena.
6.372
So people stop short at natural laws as something unassailable, as did
the ancients at God and Fate.
And they are both right and wrong. but the ancients were clearer, in
so far as they recognized one clear terminus, whereas the modern
system makes it appear as though _everything_ were explained.
F.
G. Frege
or both)!
You FALSLY claim that Dijkstra said:
"Restrict the use of the go to statement to alarm exits."
ACTUALLY he writes:
"The remark about the undesirability of the go to statement is
far from new. I remember having read the explicit
recommendation to restrict the use of the go to statement to
alarm exits, but I have not been able to trace it; presumably,
it has been made by C. A. R. Hoare."
His OWN position is:
"For a number of years I have been familiar with the
observation that the quality of programmers is a decreasing
function of the density of go to statements in the programs
they produce. More recently I discovered why the use of the
go to statement has such disastrous effects, and I became
convinced that the go to statement should be abolished from
all "higher level" programming languages (i.e. everything
except, perhaps, plain machine code)."
Jeremy Henty
Charlie-Boo wrote:
>> >> Not true! What if the code calls malloc() without checking
>> >> whether the return value is NULL? You could verify every
>> >> possible input and still see the program crash when memory is
>> >> low.
>> >
>> > Then one of the inputs to the subroutine is the amount of space
>> > available!
>>
>> This answer simply concedes that Dikstra is effectively right. The
>> number of possible values of "amount of space available" is in no
>> way "reasonably small". And we haven't even begun to consider all
>> the other ways that the code could interact with the operating
>> system.
>
> To show one example of a program for which it is not practical to
> try all possible inputs doesn't prove anything. (I am not so sure
> that you even did that, but it is not hard to do.)
My comments apply to *any* program that interacts with the operating
system non-trivially. That's a lot more than one program.
> ... The point is that Dijkstra said that debugging never proves
> that a propgram is correct,
As others have already pointed out, Dijkstra did not say this.
Regards,
Jeremy Henty
--
Roll credits over blooper outtakes
Charlie-Boo
> Actually you are just a notorious liar, Charlie-Boo (or an illiterate,
> or both)!
>
> You FALSLY claim that Dijkstra said:
>
> "Restrict the use of the go to statement to alarm exits."
>
> ACTUALLY he writes:
>
> "The remark about the undesirability of the go to statement is
> far from new. I remember having read the explicit
> recommendation to restrict the use of the go to statement to
> alarm exits, but I have not been able to trace it; presumably,
> it has been made by C. A. R. Hoare."
He presents it as an example of his principle (and doesn't refute it.)
If he quotes technical remarks even though they are not true, then
he's nuttier than I thought!
> His OWN position is:
>
> "For a number of years I have been familiar with the
> observation that the quality of programmers is a decreasing
> function of the density of go to statements in the programs
> they produce. More recently I discovered why the use of the
> go to statement has such disastrous effects, and I became
> convinced that the go to statement should be abolished from
> all "higher level" programming languages (i.e. everything
> except, perhaps, plain machine code)."
That doesn't contradict the above.
Charlie Volkstorf
Cambridge, MA
G. Frege
>
> He presents it as... <bla bla>
>
Oh, shut up!!! ***Obviously*** he did NON of that.
What HE said, was:
" I became convinced that the go to statement should be
abolished from all "higher level" programming languages."
Try to understand the meaning of this sentence, moron: obviously it
does NOT say: "I recommend to use GOTOs for alarm exits (only)."
If you STILL claim that he said what he DIDN'T say, you are just an
asshole of a liar.
F.
Charlie Volkstorf
> reasonable.
>
> Michael you shouldn't bother to much. This guy is a well know Usenet
> troll. (Try to find other threads he started...)
check out my FOM (Foundations of Mathematics) threads that unveil the
world's 1st actual Quine Atom, a formalization of the Liar including
generating new paradoxes, a debunking of Chaitin's Omega number, and a
host of other new and startling findings.
For 2,000 years plus man has grappled with the Liar paradox without
being able to resolve it. Now, at long last, I have solved the Liar
paradox. I have resolved it.
The solution is: The Liar paradox is the semantics of a Turing Machine
that gets into an infinite loop expressed in English.
I show how to generate Semantic Sentences and how I posted 1,000
Paradoxes. (I have found numerous errors and other deficiencies in
published works.)
> Actually he is claiming nonsense most of the times. (Last time he
> proved the _real_ existence of a self-containing set, etc.)
Oh, I went way beyond that. I solved 3 HyperSet Equations:
1. x = {x} Quine Atom
2. f(x) = {f(x)} Multiple Quine Atoms
3. x = {x,0} Variation on Quine Atom
I used an ingenious construction and self-reference to create
definitions that actually equate to themselves in these various
contexts.
> Actually we CAN'T show a program to be correct ONLY by testing!
> A is correct but B is not:
> since the amount of storage is _finite_. Sooner or later it will
> stop functioning correctly.
This is just repeating the mistake of leaving out an input in the
test, in this case, the amount of storage available.
> 2: if date >= 1.1.2005 have fun
> 3: print var
> 4: goto 0.
The date is the additional input.
> D: For any number N of tests to be performed, I can always
> give you a program D' that will pass ALL that tests, and still be
> faultily; it will fail for, say, number of tests > 2*N.
You are counting an unbounded input as one input, so there are an
infinite number of possible inputs. You need to test it by testing
the finite subroutines at the highest levels of abstraction in the
program.
> "program testing can best show the
> presence of errors but never their absence".
> Actually Dijkstra's is _completely_ correct. NO need to "weaken" it.
That's not true. He didn't consider the case where you do automated
exhaustive testing. He wasn't advanced enough to be able to think of
my more advanced ideas and techniques. Just I have constructed the
Quine Atom that Quine, Russell, Frege, et. al. were never able to, I
have also shown more advanced techniques that expose the errors in
Dijkstra's contensions.
> If Charlie-Boo (sic!) were a serious person I would suggest that he
> should read something about _proof by (empirical) induction_; it's
> well known that this is NOT strong enough to ensure anything.
My systems are a lot more advanced than theirs. Dijkstra was supposed
to be so good, but he made a lot of mistakes. He only informally
examined a prime number generator. I actually synthesized one, thus
making it totally formal.
> F.
You should read up on my theories. They're a lot better than the
stuff you've been reading.
Virgil
axio...@aol.com (Charlie Volkstorf) wrote:
> For 2,000 years plus man has grappled with the Liar paradox without
> being able to resolve it. Now, at long last, I have solved the Liar
> paradox. I have resolved it.
Does James S. Harris accept your solution?
Whatever you answer, or even if you don't, it creates a new liar's
paradox which should keep us all safe for another 2000 years.
Virgil
> You should read up on my theories. They're a lot better than the
> stuff you've been reading.
And do you, like Oscar Wilde, often quote yourself to spice up your
conversation?
Charlie Volkstorf
> > >
> > You can, if by a systematic analysis of the program's structure,
> > you know that the data set used to test the program with
> Yes, of course. ( You certainly noticed the word _only_ in the claim
> above? )
>
> Strange communication pattern you have:
> I : We (man) can't fly ONLY by flapping with the arms.
> You: You can, if using an airplane.
> *sigh*
> Without knowing the internal structure of a program and an appropriate
> program analysis no information concerning "eigendata" is available
> (in general).
You don't have to analyze the program's structure. You don't know the
program's structure and it is faulty anyway. You are trying every
possible set of values that are allowed by the program as input. So,
for example, if you have 3 check boxes in the input dialog, then you
try all 8 subsets of checks. If you have a 3 character field, you try
each string of length no greater than 3. It is a function of the
input form presented to you, not the program behind it. The spec may
also say that you are to assume that the input is of a given form,
e.g., it is supplied by another process that would be faulty and be
corrected if it supplied otherwise. The check for other input values
occurs elsewhere.
(This is the examination of finite primitive elements, not the
analysis of an algorithm.)
> Hence testing ALONE usually won't suffice.
Speaking of words, you have added the word "usually". Assuming this
is not an understatement, we can conclude that it is not the case that
testing alone ALWAYS won't suffice, i.e., there are cases where
testing alone does suffice, and you have admitted that Dijkstra is
wrong. Thank you. :-)
> On the other hand... what would the eigendata values have to be for a
> program of the form . . . ?
Each is not an instance of trying all values for all inputs. You are
leaving out the current amount of space available or the current date
from the input, or are allowing unbounded and thus infinite input in
one invocation of the program (so that a counter becomes unbounded.)
> Obviously we have to _analyze_ the programs FIRST to determine the set
> of "eigendata" (if it does exist).
>
> F.
Charlie Volkstorf
Cambridge, MA
http://www.mathpreprints.com/math/Preprint/CharlieVolkstorf/20021008.1/1
http://www.arxiv.org/html/cs.lo/0003071
axiomize at aol dot com
Charlie Volkstorf
>> being able to resolve it. Now, at long last, I have solved the
Liar
>> paradox. I have resolved it.
> Does James S. Harris accept your solution?
> Whatever you answer, or even if you don't, it creates a new liar's
> paradox which should keep us all safe for another 2000 years.
If it creates a new liar's paradox even if I don't answer, then what
causes the paradox's creation since there is no telling when I may
answer (the halting problem is unsolvable)?
>> You should read up on my theories. They're a lot better than the
>> stuff you've been reading.
> And do you, like Oscar Wilde, often quote yourself to spice up your
conversation?
Yes, in clever self referential ways.
Charlie Volkstorf
Cambridge, MA
http://www.mathpreprints.com/math/Preprint/CharlieVolkstorf/20021008.1/1
http://www.arxiv.org/html/cs.lo/0003071
G. Frege
wrote:
> >
> > Frege: Hence testing ALONE usually won't suffice.
> >
> Speaking of words, you have added the word "usually". Assuming this
> is not an understatement, ...
>
It WAS meant as an understatement; in fact, the truth is:
Testing ALONE won't suffice.
----------------------------------
This should be QUITE clear by what was said earlier:
Frege: Actually we CAN'T show a program to be correct ONLY by
testing!
Einstead: You can, IF by a systematic analysis of the
program's structure, you know that the data set used to test
the program with is representative.
Frege: [so] we have to _analyze_ the programs FIRST to
determine the set of "eigendata" (if it does exist).
And hence:
Frege: Testing ALONE won't suffice.
----------------------
Why don't you just shut up, stupid?!
Charlie-Boo
That doesn't prove anything. You're just looking at the wrong
sentence. Pointing to one sentence doesn't prove anything about a
different one (no matter how obnoxious you act.)
Charlie Volkstorf
G. Frege
<jer...@chaos.org.uk> wrote:
>
> My comments apply to *any* program that interacts with the operating
> system non-trivially. That's a lot more than one program.
>
Actually it's not necessary that the program interacts _with the
operating system_ in an "essential way".
Say for example you have implemented a program that should calculate
the current mean value from successively supplied integer values.
Well, and you do it this way: count the numbers of input values and
divide the sum of all input values by that number.
0: n = 1, sum = 0
1: Read input: temp
2: sum := sum + temp
3: Print: sum/n
4: n := n + 1
5: Goto 1.
Looks quite nice, doesn't it? And actually it will work in the desired
way. Hence it's correct, right?! ;-)
So let's look at a concrete implementation in, say, the language C:
#include <stdio.h>
int main(void)
{
int n, temp;
double sum;
n = 1; sum = 0;
loop:
scanf("%d", &temp);
sum = sum + temp;
printf("mean value: %f\n", sum/n);
n = n + 1;
goto loop;
return 0;
}
Well, we are quite happy with this program, aren't we?!
Actually the program works just fine...
***as long as _the number of input values_ is < MAXINT***
...and MAXINT is machine dependent! (Hence the program may or may not
fail in practice...)
F.
P.S.
Now say you are testing the program on a 64-bit machine; and your
compiler implements 64-bit "int". Then it's QUITE UNLIKELY that you
will ever face this problem while testing the program.
Now if someone compiles the code on a 80186-machine, he will probably
have (face) A PROBLEM...
michael adams
For 2,000 years plus man has grappled with the Liar paradox without
being able to resolve it. Now, at long last, I have solved the Liar
paradox. I have resolved it.
..................................................................
I object in the strongest possible terms, as follows -
No you didn't! I already did a few weeks ago, at the end of
Mr Blackburn's liar thread!
Just as has already been shown with the barber paradox, I
demonstrated conclusively that nobody is ever in a position to
make the utterance "I am a liar" in the first place.
So such a statement is a logical and ontological impossibilty.
However my solution was totally ignored because clearly there are people
around who can make a good living by simply discussing ad-nauseam
the *supposed* logical significance of completely meaningless strings
of symbols, whether these appear on paper or on a computer screen.
And all very often at the taxpayer's expense, I might add!
Yours in total disgust
michael adams
Charlie-Boo
> Charlie Volkstorf wrote -
> For 2,000 years plus man has grappled with the Liar paradox without
> being able to resolve it. Now, at long last, I have solved the Liar
> paradox. I have resolved it.
>
> ..................................................................
>
> I object in the strongest possible terms, as follows -
>
> No you didn't! I already did a few weeks ago, at the end of
> Mr Blackburn's liar thread!
>
> Just as has already been shown with the barber paradox, I
> demonstrated conclusively that nobody is ever in a position to
> make the utterance "I am a liar" in the first place.
I just did.
> So such a statement is a logical and ontological impossibilty.
> Yours in total disgust
>
> michael adams
There's nothing syntactically wrong with "This is false." It is just
the fact that it is a Turing Machine that gets into an infinite loop.
That is what people have always missed for these past 2k years. It is
the Halting Problem in English. Check out FOM (Foundation of
Mathematics) for details.
Charlie Volkstorf
Cambridge, MA
michael adams
> mjad...@onetel.net.uk (michael adams) wrote in message news:<457feaaa.02112...@posting.google.com>...
> > Charlie Volkstorf wrote -
>
> > For 2,000 years plus man has grappled with the Liar paradox without
> > being able to resolve it. Now, at long last, I have solved the Liar
> > paradox. I have resolved it.
> >
> > ..................................................................
I say
> > I object in the strongest possible terms, as follows -
> >
> > No you didn't! I already did a few weeks ago, at the end of
> > Mr Blackburn's liar thread!
> >
> > Just as has already been shown with the barber paradox, I
> > demonstrated conclusively that nobody is ever in a position to
> > make the utterance "I am a liar" in the first place.
.................................................................
Charlie interjects thus
I just did.
...............................................................
Which leads me to ask -
Given that you have just claimed to have made the utterance
"I am a liar" - and that you also claim presumably that that
utterance is supposed to actually mean something - over and above
say, "blaaaaaahh ergggggghhh blaaaaaah wheeeeeeeeee!"
Which are you Charlie ? -
given that -
A liar is somebody who by definition never speaks the truth.
And so a liar is the only person who can ever utter knowingly
false statements.
a) Again by definition, because he never the speaks the truth,
despite the fact that he can only ever utter false statements,
a liar can never utter the sentence " this statement is false".
b). A person who always tells the truth can never utter the sentence
" this statement is false".
c) A person who sometimes tells lies and sometimes tells the truth,
cannot by definition when they are telling a lie, and thus making
a false statement, utter the sentence "this statement is false"
d) A person who sometimes tells lies and sometimes tells the truth,
whenever they are telling the truth cannot utter the sentence
"this statement is false"
Which is it to be please Charlie - a), b), c), or d)?
Do you always tell lies, always speak the truth or sometimes
do a bit of both?
michael adams
Virgil
mjad...@onetel.net.uk (michael adams) wrote:
You forgot to allow e) None of the above.
michael adams
Virgil wrote -
> You forgot to allow e) None of the above.
.....................................................
I reply -
That's it! Try and cover up the truth! Rob me of my rightful
recognition by ridiculing my solution!
Now I know exactly how Harris and Correy must feel!
G. Frege
"For 2,000 years plus, man has grappled with the Liar paradox
without being able to resolve it. Now, at long last, I have
solved the Liar paradox. I have resolved it."
Charlie Volkstorf
Sure...
F.
Charlie-Boo
> "For 2,000 years plus, man has grappled with the Liar paradox
Don't you read the Bible?
We can exactly formalize the Liar paradox as a Turing Machine that
gets into an infinite loop when it attempts to evaluate "This is
false.", and at the same time is guaranteed by its construction to
return true iff the sentence is true, and false iff the sentence is
false, thus proving that "This is false." is neither true nor false.
This is analogous to finding a wff that is not provable nor refutable.
It is interesting, in hindsight, to think about all of those people
who attempted to resolve the Liar Paradox, and none of them even
considered the possibility that it is simply a Turing Machine in an
infinite loop. But hindsight is always 20-20, and so it seems so
obvious now that it has been solved.
At this great moment in the history of Mathematical Logic, I think we
should all look back at the glorious history of the Liar Paradox, and
all of the failed attempts to resolve it.
Most common are "formalizations" that only include "This is false.".
That is truly sad. It is functionally no different than a program
that merely writes the literal "This is false." and halts. Numerous
systems of this sort have been proposed, but, because they fail to
enumerate the other possibilities, or to create new paradoxes, then
they are of no value.
However, unfortunately, professors in famous universities write about
such things, and because of respect for the institution, their
proposals are published, even though they are insipid and feckless.
But now that we at long last have the actual solution to the Liar
Paradox, it is a time of rejoicing and forgetting about the
dishonesties of the past. It is time to enter a new era of
enlightenment. For, remember, Fermat's Theorem was unproved for only
350 years, and we have now solved the oldest puzzle ever known: The
Liar Paradox, over 2,000 years old.
Charlie Volkstorf
Cambridge, MA
http://www.mathpreprints.com/math/Preprint/CharlieVolkstorf/20021008.1/1
http://www.arxiv.org/html/cs.lo/0003071
George Dance
It seems to me that, when most people talk about finding a 'solution'
to the Liars Paradox, they mean finding a consistent assignment of
truth values to the sentences. OTOH, your 'solution' sounds more like
a model meant to prove that no 'solution' (in the first sense) is
possible. Is that what you claim is the proven solution?
G. Frege
wrote:
> >
> > Don't you read the Bible?
> >
Of course I do.
> >
> > It is interesting, in hindsight, to think about all of those people
> > who attempted to resolve the Liar Paradox, and none of them even
> > considered the possibility that it is simply a Turing Machine in an
> > infinite loop.
> >
Probably because the Turing Machine was not INVENTED before 1936?
Obviously the thing that some would call "your brain" is ALSO a Turing
Machine in an infinite loop. (Too bad for you that it seems to be a
very tight loop.)
> >
> > But hindsight is always 20-20, and so it seems so
> > obvious now that it has been solved.
> >
Well, actually _it seems quite obvious_, that's time to take your
pills (now), Charlie.
F.
Theo
The statement "This statement is false" is neither true nor false. It
is simply a lie, not a fact. How do you prove a lie? You can't... end
of story.
Lets move on. ;-)
Virgil
really wants, and I have seen no evidence of its solution here.
Taneli Huuskonen
Hash: SHA1
In <3df1e59f.02112...@posting.google.com>
ch...@aol.com (Charlie-Boo) writes:
[...]
>We can exactly formalize the Liar paradox as a Turing Machine that
>gets into an infinite loop when it attempts to evaluate "This is
>false.", and at the same time is guaranteed by its construction to
>return true iff the sentence is true, and false iff the sentence is
>false, thus proving that "This is false." is neither true nor false.
Yiannis Moschovakis said more or less the same over 12 years ago:
Moschovakis, Yiannis N. Sense and denotation as algorithm and value.
Logic Colloquium '90 (Helsinki, 1990), 210--249, Lecture Notes Logic,
2, Springer, Berlin, 1993.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPeedZV+t0CYLfLaVEQLQnwCcDPyhYa0+zgRjSZFsuFZnx2pytnsAnA5y
/madjxVjmzzQHcq7nxW78KIe
=9JXQ
-----END PGP SIGNATURE-----
--
I don't | All messages will be PGP signed, | The ultimate large
speak for | encrypted mail preferred. Keys: | cardinal: it's so large
the Uni. | http://www.helsinki.fi/~huuskone/ | it isn't true.
Bob Pease
"Theo" <th...@eisa.net.au> wrote in message
news:5a655fee.02112...@posting.google.com...
The first question ever asked is
"WTF!!!???"
Still unanswered.
One of the oldest questions is
Who Threw that??"
Still asked by High School teachers.
RJ P
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.419 / Virus Database: 235 - Release Date: 11/13/02
Charlie-Boo
> >
> > > "For 2,000 years plus, man has grappled with the Liar paradox
> > > without being able to resolve it. Now, at long last, I have
> > > solved the Liar paradox. I have resolved it."
> > >
> > > Charlie Volkstorf
> > > Sure...
> > > F.
> > We can exactly formalize the Liar paradox as a Turing Machine that
> > gets into an infinite loop when it attempts to evaluate "This is
> > false.", and at the same time is guaranteed by its construction to
> > return true iff the sentence is true, and false iff the sentence is
> > false, thus proving that "This is false." is neither true nor false.
> > This is analogous to finding a wff that is not provable nor refutable.
> It seems to me that, when most people talk about finding a 'solution'
> to the Liars Paradox, they mean finding a consistent assignment of
> truth values to the sentences. OTOH, your 'solution' sounds more like
> a model meant to prove that no 'solution' (in the first sense) is
> possible. Is that what you claim is the proven solution?
Yes, except that it depends on the system you are using. Since we are
using English, then the system is undecidable - there is an
undecidable proposition. In Turing Machines, that means there is a
program that neither halts yes nor halts no, i.e., it does not halt -
it loops. In theorem proving, it means a wff that is not provable or
refutable. In English, it means a sentence that is neither true nor
false.
It must exist because of the capabilities given in English. Consider
the set of Turing Machines that halt yes when run on themselves, and
the set of all other Turing Machines (its negation.) Also consider
whether the negation of a listable set is always listable. Now, "It
is true" allows us to list the true statements, and the word "not"
means we can list the complement. But it is impossible to list the
untrue statements just as it is impossible to list the Turing Machines
that don't halt yes when run on themselves. So we have a Turing
Machine that loops, and English sentences that loop. "This is false."
is one program that loops, expressed in English.
Charlie-Boo
> I think most people just missed the obvious.
>
> The statement "This statement is false" is neither true nor false. It
> is simply a lie, not a fact.
If it is a lie, then it is false, and not "neither true nor false".
> How do you prove a lie? You can't... end
> of story.
You can prove a lie if the system is not sound.
> Lets move on. ;-)
The next step is the application of my Calculus of Paradoxes
(including the Paradox Generator with the 1,000 Paradoxes that I
recently posted) to other branches of Computer Science, including:
1. Program Synthesis - Mathematical Programs
2. Program Synthesis - DataBase Programs
3. Theory of Computation (Computability)
4. Recursion Theory
5. Proof Theory / Incompleteness in Logic
6. HyperSets [see recent solution to Quine Atom and other HyperSet
Equations]
For example, to synthesize a program, we prove that a given set is
recursive or recursively enumerable, to create a program to decide or
list that set (see arxiv manuscript below.) To create
Metamathematical theorems such as Rosser's 1936 extension to Godel's
1st Incompleteness Theorem, we add the fact that if P is recursively
enumerable, then when P is true then P is provable. (I say: P is
complete.) Rosser also uses the fact that LT(x,I) is Finitely
Enumerable (we can list all natural numbers less than a given number
and then halt.) Then it is a simple matter to generate the Fixed
Point Theorem, the Recursion Theorem, and a self-outputting program.
These constructions also solve the HyperSet Equations, including x={x}
(Quine Atom), f(x)={f(x)} (multiple Quine Atoms) and x={x,0} (Quine
relative.) For example, let f(x)={x(x)}. Then f(f)={f(f)} and f(f)
is a Quine Atom (the 1st ever discovered.) (See FOM discussions.)