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

[andrew@pimlott.ne.mediaone.net (Andrew Pimlott)]

On Mon, May 28, 2001 at 10:51:02PM -0400, Bernie Cosell wrote:
> > 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.

You seem to think I have to define things in terms of an algorithm.
The definition right below entirely avoids these "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.

IMO you're too hung up on "match" as a verb.  Matching is an
abstract concept that does not have to be expressed as a process.  I
bet if you look at a textbook, you will find grammar's introduced in
terms of recursive definitions, and the algorithms derived from the
definitions.  If we have to come up with new algoriths (or even if
we find we can't write a general algorithm) for infinite strings, so
be it!

> Since that definition of 'match' has 
> no real connection to how Perl actually 'matches' PREs, what's the point?

I don't think you should (usually) think about Perl re's in terms of
how they are implemented in perl, or how they might be implemented
at all.  If you think of them as abstract objects, then the
extension to infinite strings is natural.

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

It's a good observation, but you're actually caught up on a small
point.  Due to "corner cases" like this, it is sometimes hard to
write a full 1-1 mapping explicitly.  But it is a theorem that if
you can do an injection (map everything in one set uniquely to the
second, but possibly some members in the second) in both directions,
it's just as good.  This is how you usually end up proving a 1-1
mapping exists.

So, the "obvious" mapping is an injection from [0,1) to strings
(just normalize the real number to one of the representations in the
"corner case").  To go the other way, let's use a hack: in the
ambiguious case, map the 999... version into [0,1) naturally, and
map the 000... version into [1,2) by adding one.  Since I'm sure you
agree that [0,1) is the same size set as [0,2), this is good enough.
(I'm sure there's a more elegant way around this, but it's been a
while.)

So, you are technically right that there is no obvious 1-1 mapping;
but the obvious "almost mapping" captures the idea.

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

Well, practically, this is an easy one, because an infinite string
can't have a last character.

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

Do you mean to keep running, every step adding a digit to the
string?  But then the value is indeterminite for some inputs.  You
have to feed cold, hard strings into the I-RE-matcher, so I don't
see how this argument works.  Did I miss something?  (I'll think a
little more on the way home.)

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

Andrew

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