I don't really find "If you don't try to solve the halting problem, then you can parse Perl" to be a "stronger" conclusion than "If you don't do something random, then you can parse Perl", other than, of course, the presence of high-falutin' comp sci lingo in the former.
You're kind of right. It's called minimalization. If I can solve this base problem, I can solve this more complex problem. Ex: If I can prove I can sort, I can sort in reverse, I can sort using other means etc etc etc. If I can do those things and have proven those things, I can do even more, chaining all the way.
You're minimalizing directly to undeterministic behaviour, as opposed to the halting problem. Most people chain minimalized behaviour to save time. You don't have to prove the halting problem since it's already proven. Your intuition is right. It's only awkward by the convention of, "most people don't do it like that."
I'm amused the conversation is taking place though. You're both arguing cherry pie or apple pie to be tasty. :)