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

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

"Daniel S. Wilkerson" wrote:

> 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

Dang, I meant "in binary here", of course.

> 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


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