The Cauchy/Cantor Diagonal Method

Talking about 1 + 1 = 1 again, i.e. in the context of Erez Elul’s Pile Systems:

How to construe an unique identifier out of two things?

hardgrave76-fig41.png
In this post, we rediscover an application of the Cauchy/Cantor Diagonal Method in the area of information systems described by W. T. Hardgrave in the Mid-Late 1970’s (see References at the end of this post).

„Periodically, a mathematical idea which was born in a past century finds new application in the area of information systems; such is the case with the Diagonal Method of Cauchy (1789–­1857) and Cantor (1845–1918).“

(Hardgrave 1976 – A technique for implementing, p. 88)

The Cauchy/Cantor Diagonal Method was originally used to demonstrate that the rational numbers were countable, but Hardgrave applied it to a computer implementation of „a system based on extended set theory.“

The Cauchy/Cantor Diagonal Method is a reversible mapping from the ordered pairs to the integers. This mapping is both one-to-one and onto. The importance of this mapping and its inverse is that each ordered pair <K,L> may be uniquely associated with a single integer M. Thus given K and L, M is known, whereas given M both K and L are uniquely defined.

This method of associating pairs with integers is generally called the Cauchy/Cantor Diagonal Method. Using the Cauchy/Cantor mapping, M can be directly calculated from K and L, and vice versa. Thus a table or the like need not be stored.

The next section of Hardgrave’s paper talks about the „Use of the Diagonal Mehod“. The basic problem of implementing extended set theory is one of finding a suitable machine representation for the extended set.

„Methods of representing classical sets of positive integers by bit strings are easily derived and well known (e.g. Hardgrave (15)).“

The essence of such techniques is that when a bit string is used to represent a set (S), a ‚1‘ in bit position I implies that I is element of S.

(Hardgrave 1974 – The prospects of large capacity) demonstrates bit strings as a viable representation for sets and talks about the question of their compaction. His QUATREE compaction method is based upon the idea that compaction can be performed by creating multi-level directories of four-bit packets.

Hm… four-bit packets?! For the Pile insiders, this sounds like Pile Group Management, isn’t it? But that’s another story…

…to be continued in the Pile mailing list.

——————————

References

(Hardgrave 1976 – A technique for implementing)

Hardgrave, W. T. (1976): A technique for implementing a set processor. In: ACM SIGPLAN Notices, Vol. 11, Nr. SI, p. 86–94. Available online at http://doi.acm.org/10.1145/942574.807126

(15), i.e. (Hardgrave 1974 – The prospects of large capacity)

Hardgrave, W. T. (1974): The prospects of large capacity set support systems inbedded within generalized data management systems. In: Guenther, A.; Levrat, B.; Lipps, H. (Eds.): International computing symposium 1973. ICS ; Proceedings of the International Computing Symposium 1973; 4 – 7 sept 1973. Amsterdam. North-Holland. p. 549-556

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s