Monday, September 18, 2006

Pail Challenge

Remember those old chestnuts like, "You are given a 7-quart and a 9-quart pail; return from the well with exactly one quart"?

For a>b, give the set S in terms of a and b of all possible returns from the well. Design a parametrized production system (alphabet plus rewrite rules) or, equivalently, a Turing machine to derive and return any member of S. For extra credit, generalize to any (finite) number of pails a[i].

Does an infite number of pails add anything interesting??

1 Comments:

At 7:41 AM , Blogger Gene Callahan said...

While I remember the old chestnut, I don't recall the nutcracker that opens it! Perhaps you can post it here.

 

Post a Comment

<< Home