(A Turing machine is the best and most standard theoretical model for all general-purpose languages and machines. Technically, Perl features like access to the system clock are not in the Turing machine model, but it is simpler, and entirely safe, to ignore these non-Turing Perl features. The system clock isn't going to help you parse Perl.)

Fallacious Counter-Argument: First, let's reduce the problem of Perl parsing to the issue of determining whether a function's prototype is nullary or not. If it's proved that determining nullarity is, in general, decidable, it reduces my original proof to rubble. It probably also generalizes to a full counter-proof.

Consider the following code snippet:

sub runtime_nullary {
    my $function = shift;
    return 0
        if not defined( my $prototype = prototype $function );
    return $prototype eq q{};
} ## end sub runtime_nullary

print 'nullary dunno: ';
say runtime_nullary('dunno') ? 'yes' : 'no';

print 'result is ';
say dunno +4;
[download]

First take some Perl code. It must be free of fatal errors, but otherwise can be "arbitrary". ("Arbitrary" in math-speak means "anything you like".) Now let's make 4 observations about it.

1. Something like the above snippet can placed to execute first (or early) in the run phase of the arbitrary code.
2. We can place this snippet in the arbitrary code so that we always reach the snippet and execute it.
3. Once runtime_nullary runs, we know whether the function named in its argument is nullary or not.
4. We can run runtime_nullary on any function we like, and on as many functions as necessary.

So therefore, Fallacious Conclusion: We can determine, for arbitrary Perl code, whether any Perl function has a nullary prototype or not.

First, let me concede that the Fallacious Conclusion does follow from Observations 1-4. Let me also concede that Observations 1, 3 and 4 are correct. And let me also concede that if Fallacious Conclusion is correct, my Perl Parsing Undecidability Proof (and probably any other) is kaput.

But what about Observation 2? It looks solid, but it hides a major fallacy. We reach the run phase only if we get out of the compile phase. True, this is something we usually take for granted, but if we assume the compile phase eventually ends (or that we can tell whether it will or not), we assume there is no Halting Problem in the compile phase. And if we assume that there is no Halting Problem in Perl's compile phase, we assume that the compile phase does not have Turing machine power.

Perl's compile phase does have Turing machine power, and therefore is subject to the Halting Problem. This is not just a fact, but it is exactly that property of Perl which causes Perl parsing to not, in general, be decidable. The ghost of the Halting Problem must always haunt those who seek the power of the One Universal Machine to Bind Them All.

Update, 11 Oct 2009: I simplified the code snippet a bit to focus on my point in this post. The original is on page 25 of the Fall 2008 issue of The Perl Review.

Update, 12 Oct 2009: Based on feedback from blokhead and ikegami, revised the Fallacious Counter-Proof to emphasize that the problem lies in determining nullarity for arbitrary code.