note Jeffrey Kegler You spotted an unclarity in my presentation. I was vague about what "time" the code strings are to be run. Perhaps this is better: <code> sub halts { my $machine = shift; my $input = shift; is_whatever_nullary( qq{ BEGIN { run_turing_equivalent("\Q$machine\E", "\Q$input\E"); sub whatever() {}; } } ) } </code> Using rand() is indeed more obvious and it was how I tested my code snippets (I lent my Halting Oracle to a friend and she never returned it ... but don't get me started.) I did not use it in the presentation because while it makes the proof more obvious, it's a proof of a weaker theorem. If you interpret rand() as truly random (and not as pseudo-random), then we're dealing with non-deterministic programs. Someone might then say, "as long as there is no non-determinism while compiling, Perl 5 is statically parseable." But it's not and a proof using the Turing machine simulator shows it is not. That Perl 5 is unparseable even when the code is completely deterministic is a much stronger result, and the distinction makes a difference in practice. The Turing simulation in this case is brought in for very practical reasons. I can't claim the credit for that. Adam Kennedy's hint took me in this direction. I suspect he also knew the business about rand(). But with his many hours of real life experience trying to statically parse Perl, he focused on the stronger proof -- the one that would give him the most information about what he was up against in creating [mod://PPI]. 663393 663416