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

["Daniel S. Wilkerson" <dsw@digital-integrity.com>]

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

Respectfully, your statement seems to be in error.

If by the "obvious 1-to-1 mapping" you mean write out a real in decimal but
don't allow an infinite subsequence of 1's (I would say 9's if this was base
10), then indeed you can think of a real number between 0 and 1 (lets say
0<=x<1) as an "infinite string".  However, it is perhaps more natural to just
say simply, all countably-infinite squences of 0's and 1's.  Now, there are
2^omega such sequences (more than countable), but these are not what is defined
in CS theory as a string.   A string is a finite sequence of characters from a
finite alphabet [Introduction to Automata Theory, Languages, and Computation,
Hopcroft and Ullman, p. 1]

If you only allow finite sequences as strings, as your regex /^\d+$/ seems to
(since it ends in a $), then there are indeed only a countable number.  That
is, "most" of the real numbers in [0, 1) do not end in an infinite sequence of
0's.

Daniel


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