Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site decwrl.DEC.COM
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!dec-rhea!dec-castor!postpischil
From: postpischil@castor.DEC (Eric Postpischil)
Newsgroups: net.puzzle
Subject: Language of Finite Strings is Countable
Message-ID: <1767@decwrl.DEC.COM>
Date: Wed, 19-Mar-86 09:11:29 EST
Article-I.D.: decwrl.1767
Posted: Wed Mar 19 09:11:29 1986
Date-Received: Sat, 22-Mar-86 03:06:36 EST
Sender: daemon@decwrl.DEC.COM
Organization: Digital Equipment Corporation
Lines: 18


Mitch Marks writes:
 
>      Give me a putative mapping from the natural numbers to the sentences of
> this language, and I construct a sentence which differs from your sentence #1
> in place #1, differs from your #2 in place #2, etc, yet which accords with the
> grammar.  This is easy to do: if your sentence #n has length n or greater, I
> pick the other character at position #n; if your sentence #n is shorter than n
> characters, I freely pick a or b.  My sentence is a nonempty string of a and
> b, so it's in the language.
 
The sentence constructed is not in the language because it is not of finite
length.
 
 
				-- edp
				Eric Postpischil
				"Always mount a scratch monkey."