Some Completeness Results in the Mathematical Theory of Computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some Completeness Results in the Mathematical Theory of Computation

Full text

Pdf (808 KB)

Source

Journal of the ACM (JACM) archive
Volume 15 , Issue 1 (January 1968) table of contents

Pages: 124 - 134

Year of Publication: 1968

ISSN:0004-5411

Author

Donald M. Kaplan

Department of Computer Science, Stanford University, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 27, Citation Count: 7

Additional Information:

abstract references cited by index terms peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321439.321447 What is a DOI?

ABSTRACT

A formal theory is described which incorporates the “assignment” function a(i, k, &xgr;) and the “contents” function c(i, &xgr;). The axioms of the theory are shown to comprise a complete and consistent set.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	McCARTHY, J. Towards a mathematical science of computation. Proc. IFIP Congr. 62 (1962), 21-28.
	2	Elliott Mendelson, Introduction to mathematical logic (3rd ed.), Wadsworth Publ. Co., Belmont, CA, 1987

CITED BY 7

	Greg Nelson , Derek C. Oppen, Simplification by Cooperating Decision Procedures, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.245-257, Oct. 1979
	Norihisa Suzuki , David Jefferson, Verification Decidability of Presburger Array Programs, Journal of the ACM (JACM), v.27 n.1, p.191-205, Jan. 1980
	S. Igarishi, Comments on the formal treatment of types including sets, ALGOL Bulletin
	B. J. MacLennan, Fen—an axiomatic basis for program semantics, Communications of the ACM, v.16 n.8, p.468-474, Aug. 1973
	Peter J. Downey , Ravi Sethi, Assignment Commands with Array References, Journal of the ACM (JACM), v.25 n.4, p.652-666, Oct. 1978
	D. Sarkar , S. C. De Sarkar, A Set of Inference Rules for Quantified Formula Handling and Array Handling in Verification of Programs Over Integers, IEEE Transactions on Software Engineering, v.15 n.11, p.1368-1381, November 1989
	Jack B. Dennis, Bibliography, Record of the Project MAC conference on concurrent systems and parallel computation, ACM, New York, NY, 1970