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

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

On 28 May 2001, at 21:53, Andrew Pimlott wrote:

> On Mon, May 28, 2001 at 08:30:39PM -0400, Bernie Cosell wrote:
> > On 28 May 2001, at 22:57, Abigail wrote:
> > > 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.
> 
> None of abigail's notions are fuzzy; in fact, they are very precise.
> (If you read carefully, you will notice that abigail is consistently
> precise.)  If he doesn't spell them out, it is (I think) because he
> intends to challenge you.  I may spoil his Fun this time.
> 
> An infinite string is a map from Z+ (postivite integers) to
> characters.

No problem there.  And indeed, that should be an uncountable set.

> To talk about a grammar generating an infinite string, you do have
> to extend the definitions, but the extensions are straightforward.

I'd love to hear the 'straightforward' part.  You get into the problem if 
infinite regress and non-terminating processes and non-computability and 
all sorts of interesting potential traps.


> For example, you can define "A*" to generate all (possibly infinite)
> strings comprised of (possibly infinitely many) substrings, each of
> which matches "A".  Some of the fancy constructs in Perl re's (eg,
> those that involve arbitrary Perl code) can't be extended, but all
> the conventional elements can.
> 
> Obviously, you can't test for matches against infinite strings with
> the usual algorithms; however, this does not invalidate the concept.

Ah, but it *DOES*.  And that was the very point.  Abigail was making some 
statement that a Perl RE can *MATCH* an infinite string.  What is the 
definition of 'match' in that case?  This seems to immediately get into 
the halting-problem bind: if the string does *NOT* match, then you can 
determine that in a finite amount of time, but there's no way to 
determine that the string *matches*.

And so you need to somehow come up with a definition of 'match' that will 
allow you to embrace an infinite process.  Now, I guess you can just *do* 
that [similar in spirit to the way you use "oracles" in recursive 
function theory to generate the arithmetic hierarchy].  But you've just 
done a funny thing, coming up with a non-computable definition whether an 
RE can "match" a particular string.  Since that definition of 'match' has 
no real connection to how Perl actually 'matches' PREs, what's the point?
Abigail's question *STILL* has no meaning: to ask "can you determine if a 
particular PRE "matches" a given set" basically doesn't involve Perl at 
all, but the largely arbitrary way you choose to define 'match' on 
infinite objects and how you allow yourself to represent the set.


> > > .. 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.
> 
> Be assured that Abigail has a firm grasp of such subtlety (and that
> there is such a mapping, which I think you can figure out if you
> haven't already).

You're right, I haven't.  Perhaps you can help me.  In particular, 
consider the two strings:   .49....  [9's forever] and
                            .50...   [0's forever]
If there is a 1-1 mapping, these two strings must map to different reals. 
Do you have an 'obvious' 1-1 mapping that actually separates those two 
strings and maps them to different reals?


> > 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.
> 
> IMO, refusing to allow re's to match infinite strings is no Fun.

I understand the disagreement now, I think, and I think that allowing REs 
to match infinite strings is not only not-fun, it still is utterly 
nonsensical.

The question, I guess, comes down to what it *means* to "match" an 
infinite string.  In almost every normal use of the term 'match', it is 
expected to be a deterministic, *terminating* process resulting in either 
"yes" or "no".  And so if you want to come up with some new sort of 
theory-of-languages, it sounds like the first thing you'll have to make 
precise is what you mean by "match".

For example, you mentioned about how "A*" could be a description of EVERY 
string-of-A's, including an infinite one.  If I gave you the infinite 
string from the first set ['A*'] and gave you the reasonable PRE "A*B", 
how would you go about determining if the string 'matched' the PRE?

As it turns out, it is easy to see that any such 'match' algorithm would 
be *necessarily* un-computable.  Consider: I have a simple FSM that 
generates strings for the RE-matcher to match [this is how I'm presenting 
my 'set' to Abilgail - you run the FSM and it gives you a string]

But this is a cute FSM: its input is an integer [so there are countably 
infinite strings in my set] and what it does is runs the associated 
turing machine [use whatever enumeration you like].  It runs the TM one 
step, if the TM stop it outputs a 1 and ends the string; if the TM is 
still running, it outputs a 0.

And I'm going to give theI-RE-matcher the regular expression:
     /^0*1$/

So now, for any TM, I have a procedure for deciding if the TM halts or 
not: simply do:
    die "IT HALTED!!\n" if TMSTRING(TMNUMBER) =~ /^0*1$/ ;
So whatever you do to 'extend' the machinery of 'string matching', it 
will be enough of an extension to allow it to embrace the halting 
problem.

  /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