Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site rochester.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!gatech!ut-sally!seismo!rochester!nemo
From: nemo@rochester.UUCP (Wolfe)
Newsgroups: net.philosophy,net.math
Subject: Re: Ineffable numbers
Message-ID: <13616@rochester.UUCP>
Date: Mon, 2-Dec-85 10:15:26 EST
Article-I.D.: rocheste.13616
Posted: Mon Dec  2 10:15:26 1985
Date-Received: Thu, 5-Dec-85 04:33:52 EST
References: <2467@sjuvax.UUCP> <11700014@inmet.UUCP> <667@spar.UUCP> <> <5086@cca.UUCP>
Reply-To: nemo@rochester.UUCP (Richard Newman-Wolfe)
Organization: U. of Rochester, CS Dept.
Lines: 49
Keywords: Paradox
Xref: watmath net.philosophy:3288 net.math:2583

In article <5086@cca.UUCP> g-rh@cca.UUCP (Richard Harter) writes:
>	...  There are also a
>	class of so-called semantic paradoxes of which the most
>	important is Richard's paradox.  This is, in effect,
>	the paradox being discussed [by previous posters].
>
>Richard's paradox:  Consider the set of all numbers between o and 1
>that can be uniquely characterized by English words.  Let R be the
>enumerated set of such numbers.  Define r as the real number between
>0 and 1 whose n'th digit is the cyclic sequent of the n-th digit
>of the n-th number in the enumeration under consideration.  Then
>r has been defined by the above English sentence and yet is not a
>member of R by construction.
>
>	Semantic paradoxes are resolved by recognizing that not
>	all definitions are effectively computable.  In the case
>	of Richard's paradox the problem is that there are English
>	sentences which purport to specify numbers but for which
>	there is not way to determine what that number is.  The
>	particular importance of Richard's paradox is that Godel's
>	incompleteness theorem is based on a formalization of
>	Richard's paradox.
>
>				Richard Harter, SMDS
>				decvax!cca!g-rh
Thanks for the roundup of famous paradoxes.  The problem is not limited
to English (or any natural language), as pointed out by G. L. Peterson
("Succinct Representation, Random Strings, and Complexity Classes", Univ. 
of Rochester CS Dep't. TR 69, Aug. 1980.  Also Proc. 21st FOCS), but is
a danger possible with any descriptive system.  He starts with another
paradox similar to Richard's, namely a variation of Berry's paradox (see
Whitehead & Russell, _Principa_Mathematica_):
  "The smallest number requiring more than a hundred words to describe" is
ill-defined since it has just been described with fewer than 100 words.

Peterson goes on to relate succinctness of representation to randomness,
and shows that "the existence of certain strings which are random with
respect to one measure and not random for another measure indicates the
difference between the two corresponding complexity classes."

Just thought those interested in this stuff might like another pointer...
Nemo
-- 
Internet:	nemo@rochester.arpa
UUCP:		{decvax, allegra, seismo, cmcl2}!rochester!nemo
Phone:		[USA] (716) 275-5766 school 232-4690 home
USMail:		104 Tremont Circle; Rochester, NY  14608
School:		Department of Computer Science; University of Rochester;
		Rochester, NY  14627