Hercules is battling a hydra. He manages to sever a head, but finds that a new head is generated according to the following rule: We move down one segment from the point where the head was severed and make a copy of the entire subtree above that point. Worse, the rate is increasing — the nth stroke of Hercules’ sword produces n new subtrees.
What will happen? The situation certainly looks dire, but, amazingly, Hercules cannot lose. No matter how large the hydra is, and no matter the order in which he severs the heads, he will always kill the hydra in finitely many turns.
Why? With each step, the complexity in the network is migrating toward the root — and that can’t continue forever. “We basically say that whenever something goes on K steps away from the root, it’s infinitely times worse than anything that is going on K-1 steps away from the root,” Comenius University computer scientist Michal Forišek explains in Slate.
“Now, whenever you kill a head, you very slightly simplified something that is K steps away. And even though you get a lot of new stuff in return, all that stuff is only K-1 steps away, and hence the entire result is still simpler than it was before.”
(Laurie Kirby and Jeff Paris, “Accessible Independence Results for Peano Arithmetic,” Bulletin of the London Mathematical Society 14 , 285-293.)