Abstract
The "intermittent assertion" method for proving programs correct is explained and compared to the conventional axiomatic method. Simple axiomatic proofs of iterative algorithms that compute recursively defined functions, including Ackermann's function, are given. A critical examination of the two methods leads to the opinion that the axiomatic method is preferable.
This research was supported by the National Science Foundation under Grant MCS76-22360.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Manna, Z. and R. Waldinger. Is "sometime" sometimes better than "always"? CACM 21 (February 1978), 159–171.
Hoare, C.A.R. An axiomatic basis for computer programming. CACM 12 (October 1969), 576–580, 583.
Dijkstra, E.W. A Discipline of Programming, Prentice Hall, 1976.
Knuth, D.E. The Art of Computer Programming, Vol. I, Addison-Wesley, Reading, Mass. 1968.
Burstall, R.M. Program proving as hand simulation with a little induction. Proc. IFIP Congress 1974, Amsterdam. (308–312).
Topor, R.W. A simple proof of the Schorr-Waite garbage collection algorithm, to appear in Acta Informatica?
Gries, D. The Schorr-Waite graph marking algorithm. Computer Science, Cornell University, 1977. Submitted to Acta Informatica.
Gries, D. An exercise in proving parallel programs correct. CACM 20 (December 1977), 921–930.
Soundararajan, N. Axiomatic proofs of total correctness of programs. NCSDCT, Tata Inst. of Fundamental Research, Bombay, India, 1978.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1979 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Gries, D. (1979). Is sometimes ever better than always?. In: Bauer, F.L., et al. Program Construction. Lecture Notes in Computer Science, vol 69. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014664
Download citation
DOI: https://doi.org/10.1007/BFb0014664
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-09251-3
Online ISBN: 978-3-540-35312-6
eBook Packages: Springer Book Archive