Andy's Math/CS page

Tuesday, May 08, 2007

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!

Labels: ,


  • Interesting puzzle. In order to prevent a cat from climbing up higher levels than n, you have to cut all the branches at n for otherwise, there will be a branch available for the cat to take and go onto a higher level. However, if you cut the branches at level n, then the tree would not grow anymore.

    The only other solution I can think of is controlling each cat's progress up the tree by cutting some of the higher accessible branches. The only problem is that n will start increasing at some point--after cutting all the branches except for one (since you want the tree to grow), cats will have no choice but to go up that branch and higher.

    By Anonymous Anonymous, at 3:01 PM  

  • On another note, I really like reading your blog and would really appreciate if you could activate RSS feeds on blogger so that we viewers may easily check if there are new posts. Thanks.

    By Anonymous Anonymous, at 3:04 PM  

  • Thank you eko1. I think my feed is working now (please let me know).

    For this puzzle, as you say, it's definitely NOT the case that you can fix some n, n = 100 say, and then prevent all cats from getting past level 100.

    It's also true that any succesful strategy must be 'adaptive', i.e. depend on the actions taken by the cats. This follows from Konig's Lemma, see 'Trees and Infinity Part I'.

    By Blogger Andy D, at 4:12 PM  

  • Thanks. It works. I will read part I of Trees and Infinity since I haven't read it yet.

    By Anonymous Anonymous, at 4:43 PM  

  • It looks to me as though we can label each cat C with a different integer n(C) and prune the tree at the point where that cat has climbed n(C) levels.

    If n(C) = C then the resulting tree is a bit spindly (in the worst case, where all the cats chose different routes, it only has one branch at each level, the other one having been pruned). But we can make n(C) = f(C) for some fast-growing computable function f and have a much bushier tree.

    By Blogger Gareth Rees, at 3:24 PM  

  • Well done, Gareth!
    It seems the optimal pruning strategy would strike some balance between bushiness and cat height, since no fire department I know of would rescue a cat at a height Ackermann(5, 5).

    In the dogs puzzle, the outcome, even with a successful strategy, is much less preordained in its structure. One has to be flexible about who gets to go how far down the tunnel, and how many times a dog can be woken up.

    By Blogger Andy D, at 4:55 PM  

  • I can't figure out how to post a comment to your dogs post (there's no comments link for that post) so I'll add it here.

    Label the dogs with different integers. On day n we feed steak to the dog labeled d if and only if dn and that dog cannot wake up any dog with a lower label (i.e. it has gone further down than all dogs with lower-numbered labels).

    No dog proceeds infinitely far. Proof by induction. Dog 1 is fed on day 1 and is never woken up since we never feed steak to any dog that could wake it up. Now suppose dogs 1 to k reach no further than distance N(k) and consider dog k+1. If it never goes further than N(k) we are done. Otherwise, since it has gone further than N(k) it cannot thereafter wake up any dog with a lower label. So on the day it passes its lower-numbered packmates (or day k+1, whichever is later) we feed it steak, it goes to sleep, and it is never woken up since all lower-numbered dogs (the only ones which might be allowed to wake it up by our rule) never get further than N(k) by hypothesis.

    By Blogger Gareth Rees, at 8:50 PM  

  • P.S. I like the way you've presented these results as puzzles.

    By Blogger Gareth Rees, at 8:51 PM  

  • Awesome! How long did it take you to solve, if I may ask? Because in the computability-theoretic setting, it took 12 years to formulate this strategy and successfully apply it to Post's problem on existence of r.e.-incomplete Turing degrees. (And, I'll add, it took me a long friggin' while to understand in that setting.)

    If it seems simpler with dogs and steaks then I feel my efforts have been rewarded. The remaining step is just to understand how Friedberg-Muchnik and other priority applications map onto dogs and steaks.

    Also, if anyone out there understands Infinite Injury and wants to devise a puzzle version to help me understand it, I'd be very grateful.

    PS. I've enabled comments on the 'Dogs' post, don't know why it was disabled.

    By Blogger Andy D, at 9:40 PM  

  • PS Thanks also for your feedback. I try to exposit math as well (and I'll have more time for that when summer rolls in), but puzzles are key as far as I'm concerned.

    By Blogger Andy D, at 9:42 PM  

  • It took me about half an hour. But you basically gave the game away with the word "priority"!

    By Blogger Gareth Rees, at 7:25 AM  

  • Oh, and my condition dn is unnecessary; we may as well feed all the dogs that can't wake lower-numbered dogs.

    By Blogger Gareth Rees, at 7:30 AM  


    By Blogger Gareth Rees, at 12:56 PM  

  • Oh, that is outstanding. :)

    By Anonymous Anonymous, at 3:40 PM  

  • zC3h3s Your blog is great. Articles is interesting!

    By Anonymous Anonymous, at 4:35 AM  

  • vKUAdo Nice Article.

    By Anonymous Anonymous, at 2:04 PM  

  • Hello all!

    By Anonymous Anonymous, at 3:38 PM  

  • Magnific!

    By Anonymous Anonymous, at 3:16 PM  

  • Is so interesting I like to know more about it is nice.

    By Anonymous Young Women Older Men, at 6:51 PM  

  • Is an funny post and a good idea I have this problem but now I know what I can do.

    By Anonymous UK Online Pharmacy, at 5:10 PM  

  • thanks I was looking the part III

    By Anonymous stomach flu symptoms, at 5:09 PM  

  • Excellent blog, I'm looking for information on how to improve my health, so I would like to help me with advice on the subject, thanks!

    By Anonymous health wellness center, at 10:42 AM  

  • Hi
    That cat is really so cute. I like that cat........Thanks.

    kamagra online, online generic levitra , womens health.

    By Anonymous Ggeneric ViagraFor Men, at 2:02 AM  

  • I have never ever come across such a wonderful piece of information. Today I am proud to say that I have finally gain knowledge on this topic and here on I shall also spread the same preaching ahead so that the world become a better place to live in.

    By Anonymous Kamagra, at 1:26 AM  

  • Thanks a lot for this great information.

    Smith ALan

    By Anonymous generic viagra for men, at 2:18 AM  

  • Please one more post about that.I wonder how you got so good. This is really a fascinating blog, lots of stuff that I can get into. One thing I just want to say is that your Blog is so perfect

    By Anonymous gloria viagra, at 11:40 PM  

  • Your blog is outrageous! I mean, Ive never been so entertained by anything in my life! Your vids are perfect for this. I mean, how did you manage to find something that matches your style of writing so well? Im really happy I started reading this today. Youve got a follower in me for sure!

    By Anonymous cheap no prescription viagra, at 5:26 PM  

  • Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.

    By Anonymous Coach Factory Online, at 2:28 AM  

Post a Comment

<< Home