[net.puzzle] Language of Finite Strings is Countable

postpischil@castor.DEC (Eric Postpischil) (03/19/86)

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."