Re: [FWP] japhy had a silly idea...

["Bernie Cosell" <bernie@fantasyfarm.com>]

On 28 May 2001, at 22:57, Abigail wrote:

> On Mon, May 28, 2001 at 02:49:34PM -0400, Bernie Cosell wrote:
> > On 28 May 2001, at 10:56, by way of owner-fwp@technofile.org wrote:
> > 
> > > that matches an unbounded set of strings. remember, there is more then 1
> > > infinity. there are infinite infinities!
> > > 
> > > a aa aaa aaaa aaaaa .................................... (infinity)
> > 
> > Yeah, but in this world there's only one infinity, since everything is 
> > constrained to be countable.
> 
> 
> Well.... only if you match against finite strings. However, regexes
> can match infinite strings as well.

No they can't.  What you're saying is meaningless on two fronts: first 
you seem to have a somewhat fuzzy notion of what an 'infinite string' is, 
and second you have an equally fuzzy notion of what a "match" is against 
a grammar/expression.  Even context-sensitive expressions [i.e., touring 
machines, which are *broader* than even Perl REs] can only generate 
countable languages.

> .. And since there is an obvious,
> 1-to-1 mapping between the set of reals between 0 and 1 and the set of
> strings (including the infite length strings) consisting of digits only,
> and each such a string is matched by /^\d+$/, it's not true that a set
> matched by a regex is of countable size.

First off, there is *NO* 1-1 such mapping, but that's a math subtlety 
that doesn't really matter, obvious to you or not.

but more clearly, you're just wrong on the face of it.  First, going from 
the RE to the language, you can enumerate every string that /^\d+$/ 
matches and the set will be completely countable.  Period.  YOu can put 
the set of strings generated-by [or matched-by] that RE into 1-1 
correspondence with the Integers, and so it is countable.

And if you go the _other_ way, you'll see how clearly your argument is 
fallacious.  Look at the old fallacy at how the integers and ther reals 
between (0,1) are of the same cardinality: use another "obvious" decimal 
expansion of the reals between (0,1) and just reverse it around the 
'decimal point' and !voila! you have the natural numbers [and so one-
eighth, .125, mapes to five-hundred-twenty-one, etc, etc]. and for each 
integer, you just reverse it and come up with a 'real'..  no problem!

I think you're confused by the difference between "finite but unbounded" 
and "infinite", which are quite different notions.  Finite but unbounded 
keeps you countable, and that's what *all* grammars get you [even fancier-
than-RE ones, like turing machines/context-sensitive]; to get to 
'infinite' you need to move to a wholly different level.

  /Bernie\

-- 
Bernie Cosell                     Fantasy Farm Fibers
mailto:bernie@fantasyfarm.com     Pearisburg, VA
    -->  Too many people, too few sheep  <--          

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe