Trees and Infinity, part III

(Hat tip to Gareth--my first fan art!)

Today, a computability theory-inspired quickie puzzle. Can you face down the infinite in its many guises?

Cats in a Tree

Some GMO-contaminated sludge washed onto your property during the latest freak weather event. A few weeks later, a mysterious tree has sprouted on the lawn, and its progress is astounding--every day, a new layer of binary growth appears:



This would be peachy, but there's a problem: your neighborhood suffers from a plague of cats. Mangy, poorly drawn, tree-climbing cats:



On any given day, some (finite) number of cats may start climbing the tree, or continue their climb from a previous day. What they don't know how to do is come down, not even a single level.
The cats all have irate, protective owners. They want you to cut down this cat sinkhole at once (after rescuing their pets). But you're not going for that--you want the world's largest tree, with unending growth.

Here's the compromise you'd like to offer the owners: a guarantee that every cat C will eventually be prevented from climbing above some level n (which may depend on C).

To achieve this, you have the following means: on any day, you can climb to any number of nodes of the tree and strip the bark there, preventing further growth above the stripped nodes.
Of course, stripping the root node would stop the cats. The challenge, again, is to achieve unending growth as well (though not necessarily the full binary tree).

Good luck!



***

This puzzle models the theorem that there exists an infinite recursive tree with no infinite recursive path. (Interestingly, however, no recursive tree T can have the Halting problem computable with the aid of an arbitrarily chosen infinite path from T. Promise problems are subtle...)

Can the whole theory of computability be 'sweetened up' this way, like the Flintstones vitamins I gobbled up in my youth? Here's a proposal: once students understand programs' capacity to simulate other programs and other computational models, dovetail search procedures, and other 'infrastructural' techniques, it may be preferable to actively 'forget' the computational statement of a problem one aims to prove.
So, in the above puzzle, the cats correspond to different simulated programs in an enumeration, but we are so profoundly unable to predict in advance the behavior of these programs that it might be better to think of the situation adversarially--hence, mischievous cats who do just as they please.
Of course, one could also make a case for the aid to visualization, and possibly generalization, given by the metaphoric puzzle format, but here I mean specifically to ask whether metaphors might help students develop a stronger familiarity with the black-box methodology of computer science.

Next time: the Finite Injury method!