| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 813.1 | A paradox discussed in the NOVA show. | STAR::HEERMANCE | Martin, Bugs 5 - Martin 0 | Fri Jan 08 1988 13:37 | 16 |
| A librarian is compiling a catalog of the books in her
library. Once she is finish she has a problem. Does she
put an entry in the catalog for the catalog? It is a book
in her library. She chooses not to do so.
At the Library of Congress in Washington they have copies
of all of these catalogs. Some of them the librarian put an
entry for the catalog, others do not contain an entry. The
head librarian decides to make a catalog of catalogs which do
not list themselfs. Once he is finished he has a problem.
Does he place an entry in this catalog for this catalog? If
he does then his book is in error since it is a catalog of
catalogs which do not list themselfs and thus since it lists
itself it is in error. However, if he does not put an entry
in it then is is incomplete since there exists one catalog (itself)
which does not list itself and for which no entry exists.
|
| 813.2 | they never tell the end of the story | ZFC::DERAMO | Daniel V. D'Eramo | Fri Jan 08 1988 14:56 | 9 |
| Re .1:
... so the clever head librarian renamed the catalog to
"Master Catalog of All Those Catalogs (except this one) that
do not List Themselves"
... and then phoned his/her brother, who works as a barber in the
small town of Seville, to tell him of his/her ingenuity.
|
| 813.3 | Make a minor change! | JON::MORONEY | Question Authority (and the Authorities will question you) | Fri Jan 08 1988 16:30 | 4 |
| If the librarian makes a catalog of catalogs that list themselves instead, he
can't go wrong!
-Mike
|
| 813.4 | On the lighter side | SQM::HALLYB | You have the right to remain silent. | Sun Jan 10 1988 22:44 | 17 |
| Alternatively, the librarian makes a list of "Catalogs that do not
list themselves" and calls it, say, a "Compendium" instead of a
"catalog". Paradox lost.
All the other national librarians do the same sort of thing with
their libraries, and ship off to the U.N. Library their National
Compendium of Catalogs that Do Not List Themselves. The U.N.
l�brarian, unable to comprehend the difference between a "Catalog"
and a "Compendium", arranges for a Librarians' Confere�ce in Seville,
where the keynote speaker, coincidentally a local lady barber, explains
how careful definitions are required in order to avoid paradoxes.
Proceedings of the First Annual Seville Librarians' Convention are
published and distributed to all the National Librarians. Regrettably
the Proceedin�s fail to mention themselves, so National Librarians
catalog them in a catalog named "Proceedings of Proceedings that
do not discuss themselves". These are sent back to the U.N. ...
|
| 813.5 | why not a bearded man? | ZFC::DERAMO | Daniel V. D'Eramo | Mon Jan 11 1988 10:08 | 5 |
| Re .-1:
>> ... lady barber ...
So *that*'s the solution! It's a lady barber! No more paradox.
|
| 813.6 | What's the Short Cut? | STAR::HEERMANCE | Martin, Bugs 5 - Martin 0 | Mon Jan 11 1988 17:12 | 7 |
| The show also discussed prime numbers of the form 2^n-1. An
example is 2^64-1 is prime. They mentioned the largest prime
of this form known took a week to calculate on a Cray using a
short cut method (ie not the sieve). Does anybody know what
this short cut is?
Martin H.
|
| 813.7 | say it isn't so! | ZFC::DERAMO | Daniel V. D'Eramo | Mon Jan 11 1988 18:25 | 6 |
| 2^64 - 1 is not prime (neither is 2^64 + 1).
See note 2 and its replies for a list of known primes of the form
2^n - 1, and a primality test for numbers of this form.
Dan
|
| 813.8 | Whoops | STAR::HEERMANCE | Martin, Bugs 5 - Martin 0 | Tue Jan 12 1988 11:48 | 6 |
| Re .7
Thanks for the pointer to note 2. Sorry about 2^64 - 1 my
memory must have been faulty and I didn't attempt to verify that
it was prime.
Martin H.
|
| 813.9 | library paradox cleared up | VIDEO::OSMAN | type video::user$7:[osman]eric.vt240 | Fri Jan 15 1988 12:21 | 12 |
| My first reaction to the library paradox is that since the catalog
of incomplete catalogs is being composed at the Library of
Congress, and is a compilation of the catalogues of town libraries,
it might as well be titled
Catalogue of Incomplete Town Library Catalogues
Since this is a Library of Congress Catalogue, and since the Library
of Congress is not a *town* library, then this catalogue itself
definitely should not be listed within itself.
/eric
|
| 813.10 | By Zermaelo, I think he's got it! | SQM::HALLYB | You have the right to remain silent. | Fri Jan 15 1988 12:52 | 6 |
| Re: .-1 Right on, Eric. What you have to do is honor the so-called
"Axiom of Regularity", by which sets are not allowed to be members
of themselves. This prevents us from defining sets that are too big
to permit a consistent set theory.
John
|
| 813.11 | It's unavoidable! | STAR::HEERMANCE | Martin, Bugs 5 - Martin 0 | Fri Jan 15 1988 16:58 | 9 |
| Re: this whole problem
The library is a word metaphore for the general problem of
consitency versus completeness. Word games may be played to try
and make this example false but the underlying problem remains.
Basically a system may either be complete (by containing
everything) and take the penalty of having inconsistencies or
it may be consistent and take the penalty of being incomplete.
The "Axioms of Regularity" take the later approach by limiting
the kind of set which may be defined.
|