Dogs in the Mineshaft
A couple posts ago I described some shenanigans with cats in a binary tree.
But that was just the front yard. The back yard is worse: it contains the opening of an old mineshaft that descends infinitely far into the earth's depths.
Well, there's some funky smell down there that dogs just have to investigate. So, every day, some finite number of dogs may enter or go further down the (unbranching) shaft. They never go back upwards. Here's the scene:
As before, you've got angry owners on your hands. You refuse to close off the shaft (it's too nifty) but again you're willing to try and ensure that any individual dog descends only finitely far into the shaft. Your tool this time: it turns out that after enjoying a good steak, a dog will curl up and fall asleep indefinitely.
The difficulty is that, before eating any steak you give it, the dog may carry it arbitrarily far further down the tunnel. If it passes sleeping dogs, they may be awakened by the steak aroma, and resume their descent.
Money, time, and steaks are no object, and you can outrun the dogs, who won't smell the steaks if they're sealed in your coat pocket. Can you keep your promise to the owners?
To get you started, consider a simple but unsuccessful strategy of giving a steak to every dog every day. The problem is that some dog D may have a sequence of 'accomplice' dogs: every time D falls asleep, a new accomplice will run into the tunnel and hang out above D in the shaft. When you give the accomplice a steak, it'll scamper past D, who'll rouse and go further. In fact, it may happen that every dog goes infinitely far down the tunnel!
Another simple idea is to give a steak every day to the dog furthest down the tunnel, if that dog is not already asleep. This avoids ever waking up sleeping dogs (assuming that the previous day's steak has had its effect; if not we can just wait longer), but it falls victim to a 'rear-guard' attack: a dog that trails constantly just above/behind the current leader.
***
This is a challenging puzzle (unless there's a glitch in the set-up, which I've checked over). But it's well worth thinking about, because the solution strategy--the 'finite injury' or 'priority' method of Friedberg and Muchnik--revolutionized computability theory. Some would say it marked the end of its comprehensibility to outside observers, but I'm optimistic that is not the case. The ingenious strategy is lovely, simple, and, fingers crossed, easier to see in a puzzle setting. I will discuss the solution in a future post, so stay tuned.
Update: Scratch that, Gareth Rees has solved the puzzle and clearly explained the solution for us, in the comments section of 'Trees and Infinity, part III'. I may still talk more in the future about its significance to computability.
But that was just the front yard. The back yard is worse: it contains the opening of an old mineshaft that descends infinitely far into the earth's depths.
Well, there's some funky smell down there that dogs just have to investigate. So, every day, some finite number of dogs may enter or go further down the (unbranching) shaft. They never go back upwards. Here's the scene:
As before, you've got angry owners on your hands. You refuse to close off the shaft (it's too nifty) but again you're willing to try and ensure that any individual dog descends only finitely far into the shaft. Your tool this time: it turns out that after enjoying a good steak, a dog will curl up and fall asleep indefinitely.
The difficulty is that, before eating any steak you give it, the dog may carry it arbitrarily far further down the tunnel. If it passes sleeping dogs, they may be awakened by the steak aroma, and resume their descent.
Money, time, and steaks are no object, and you can outrun the dogs, who won't smell the steaks if they're sealed in your coat pocket. Can you keep your promise to the owners?
To get you started, consider a simple but unsuccessful strategy of giving a steak to every dog every day. The problem is that some dog D may have a sequence of 'accomplice' dogs: every time D falls asleep, a new accomplice will run into the tunnel and hang out above D in the shaft. When you give the accomplice a steak, it'll scamper past D, who'll rouse and go further. In fact, it may happen that every dog goes infinitely far down the tunnel!
Another simple idea is to give a steak every day to the dog furthest down the tunnel, if that dog is not already asleep. This avoids ever waking up sleeping dogs (assuming that the previous day's steak has had its effect; if not we can just wait longer), but it falls victim to a 'rear-guard' attack: a dog that trails constantly just above/behind the current leader.
***
This is a challenging puzzle (unless there's a glitch in the set-up, which I've checked over). But it's well worth thinking about, because the solution strategy--the 'finite injury' or 'priority' method of Friedberg and Muchnik--revolutionized computability theory. Some would say it marked the end of its comprehensibility to outside observers, but I'm optimistic that is not the case. The ingenious strategy is lovely, simple, and, fingers crossed, easier to see in a puzzle setting. I will discuss the solution in a future post, so stay tuned.
Update: Scratch that, Gareth Rees has solved the puzzle and clearly explained the solution for us, in the comments section of 'Trees and Infinity, part III'. I may still talk more in the future about its significance to computability.
Labels: computability, puzzles
posted by Andy D at
11:41 PM
0 Comments:
Post a Comment
<< Home