Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re^4: Perl is not Dynamically Parseable

by Jeffrey Kegler (Hermit)
on Oct 13, 2009 at 16:13 UTC ( #800936=note: print w/replies, xml ) Need Help??

in reply to Re^3: Perl is not Dynamically Parseable
in thread Perl is not Dynamically Parseable

The proof looks like it goes through. One reason mathematicians do multiple proofs (aside from the fact that subsequent ones tend to be better) is that they are rhetorical devices. Different proofs speak to different audiences. Allow me to comment on a trade-off made in this version.

This proof uses Perl's rand builtin, while my efforts treat Perl as a Turing machine. The rand-based proof could be read as stating "Perl parsing is undecidable if you use rand, time or some other non-deterministic builtin".

Similarly, you could read the Turing-machine-based proofs as saying "Perl parsing is undecidable if you use Turing-equivalent control constructs." If you allow no transfers of control at all, clearly the compile phase will terminate, and my proofs no longer go through.

The different proof tactics give the two proofs different rhetorical effect. It's subjective, but subjective matters. A lot depends on whether you see Turing-equivalent control flow constructs or non-deterministic builtins as "core" features.

One thing you might do, if you're interested, is a reduction of Perl parsing to some form of Goldbach's Conjecture. This would not be a proof of undecidability, unless and until Goldbach's Conjecture is found undecidable. Instead it would amount to proof that Perl parsing is equivalent to a really hard and currently unsolved problem.

  • Comment on Re^4: Perl is not Dynamically Parseable

Replies are listed 'Best First'.
Re^5: Perl is not Dynamically Parseable
by ikegami (Pope) on Oct 13, 2009 at 17:04 UTC
    The compile phase not terminating is not a problem, and it doesn't show that Perl cannot be parsed.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://800936]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2018-01-23 21:57 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (254 votes). Check out past polls.