The entire language is available at compile time (via BEGIN blocks). I think that this fact makes any distinction between "parsing perl" and "executing perl" a little artificial & disingenuous in the context of this undecidability proof.

Anyway, since the entire language is available in BEGIN blocks, the proof does not crucially rely on subroutine prototypes. They just provide a convenient "parsing property" (clearly, determining the prototype of a sub is something that should result from "parsing") in which to effect the result. Any aspect of the language that you want to call a "parsing property" can be used. One that comes to mind is whether a loaded module returns a true value or not (and therefore whether the "parse" succeeds) -- this is something that happens during BEGIN phase.