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

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

Let me briefly say why I think this discussion was worth having,
then mercifully let us get back to Perl.

Take the following string in a two letter alphabet:

    10100100010000100000...

This corresponds (by the infamous "obvious" mapping) to the base two
number

    .10100100010000100000...

which is clearly irrational.  Irrational numbers don't repeat, so
you might think it couldn't match a regular expression (in the sense
of my second message).  But what about (10+)+ ?  Yup, seems to work.

But how would you write a program to test this match?  You first
need to figure out what it even means to take an infinite string as
input!  More precisely: what questions can you ask about the string?
If all you can ask is "what character is at position N", you're
hosed because you will never know about the whole string.  On the
other extreme, I hope you can't ask "does the string match pattern
X", because that would make the program pretty easy!  So what's the
in between?  How do you describe the pattern of an infinite string
to a program?

In general, I'm sure you can't (there are deep results that show
that numbers can be patternless in a fundamental sense)--so I
readily concede that you can't write a general re matcher for
infinite strings.  But if the mind is an algorithm, there must be
some way to express the above example, and a program that solves it.

Fun,
Andrew

PS.  Happy to continue off-list.

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