Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site sphinx.UChicago.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!gargoyle!sphinx!mmar
From: mmar@sphinx.UChicago.UUCP (Mitchell Marks)
Newsgroups: net.puzzle
Subject: Re: truth machine clarification**2
Message-ID: <1801@sphinx.UChicago.UUCP>
Date: Fri, 14-Mar-86 03:46:37 EST
Article-I.D.: sphinx.1801
Posted: Fri Mar 14 03:46:37 1986
Date-Received: Sun, 16-Mar-86 08:45:25 EST
References: <423@watdragon.UUCP> <2664@pucc-h> <394@link.UUCP> <2109@jhunix.UUCP> <11581@watnot.UUCP> <2694@pucc-h>
Reply-To: mmar@sphinx.UUCP (Mitchell Marks)
Organization: U Chicago
Lines: 44

In article <2694@pucc-h> ags@pucc-h.UUCP (Dave Seaman) writes:
>Obviously one can speak of infinite sequences of characters, but I see no
>justification for calling these "sentences."  A "sentence" is a sequence of
>symbols which can be parsed according to the rules of some language.  Any
>language which can be expressed in EBNF form has sentences of finite length
>only.
>-- 
>Dave Seaman	  					pur-ee!pucc-h!ags


    I don't see that.  Consider the "john is very ... very tired" sequence
from my previous posting.  Here's a CFG (equivalent to BNF) for a similar
language:

S -->  Dave is wrong.
S -->  Dave is <VERYSTRING> wrong.
VERYSTRING --> very
VERYSTRING --> <VERYSTRING> very

Or perhaps he's right, if he just means that any particular sentence
is of finite length.  But as long as that length is unbounded, you
still haven't guaranteed a countable language.  Here's another grammar:

S --> aS
S --> bS
S --> a
S --> b

The language is any nonempty string of a and b.  Any particular sentence
is finite, but the language is ripe for a diagonal argument showing that
it's uncountable.    Readers for whom the construction is obvious,
please skip to end.
     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.  Is it
on your list?  You have it as #1307?  No, it differs in position #1307.
-- 

            -- Mitch Marks @ UChicago 
               ...ihnp4!gargoyle!sphinx!mmar