We can think of a computably enumerable (or c.e.) set as a bag which some computer program puts more and more numbers into over time. The set then consists of all numbers which are in the bag from some point on (i.e., the numbers which are eventually put in the bag by the program). Suppose […]
Let be the set of all such that the th Turing machine halts. (For these puzzles, we will assume that Turing machines are always run on a blank initial state, i.e., they take no input.) Recall that is computably enumerable, but not decidable. Puzzle #1. Describe a winning strategy for the following game: You are […]
Here’s a puzzle: You and Bob are going to play a game which has the following steps. Bob thinks of some function (it’s arbitrary: it doesn’t have to be continuous or anything). You pick an . Bob reveals to you the table of values of his function on every input except the one you specified […]
In Joel David Hamkin’s paper Supertasks and Computation, he relates the following puzzle: Suppose that you have a countable infinity of dollar bills, and one day you meet the devil, who offers you the following bargain: In the first half minute from now, the devil will give you two dollar bills, and take one from […]
In 1992, the philosopher George Boolos gave what he called the “Hardest Logic Puzzle Ever”, which he attributed to Raymond Smullyan. In 2008, a clever paper by two graduate students, Brian Rabern and Landon Rabern, appeared in the philosophical journal “Analysis” which gave a simpler solution to the puzzle than Boolos gave—and furthermore claimed that […]
Peter Winkler‘s excellent book Mathematical Puzzles: A Connoisseur’s Collection has in it the problem of finding a partition of into disjoint non-trivial circles. (Here “non-trivial” means “not a point.”) Winkler gives a very clever solution which is purely geometric. Later, I read the same problem in Krzysztof Ciesielski‘s excellent book Set Theory for the Working […]
XOR's Hammer 