Circular Puzzle

Puzzles of various sorts have been popular on the math blogosphere lately, so I thought I'd make my own modest contribution. As puzzles go, there is not very much to this one -- no calculations are necessary, you can just look at it and visualize the answer. But the backstory that goes with it is mildly amusing. This appeared as a question on the SAT exam, back many years ago when I was an undergrad.

Imagine a circle of radius 1 unit, sitting on top of a larger circle of radius 3 units, like so: Now suppose that the smaller circle rolls around the perimeter of the larger circle until it returns to its starting position. In the course of doing this, how many rotations about its axis will the smaller circle make?

Before going on, you might want to take a moment to think about what the answer should be... Okay, ready? This particular problem was featured in a story in the news because the answer key used to score the SAT had the wrong value for this question. Let's just call it x for the time being. A high school student who sat for the exam realized that the correct answer should be y, and the math scores had to be retabulated for everyone who took the SAT that session.

The story appeared in our local paper over the weekend. The following Monday, the professor for my differential equations class, who also happened to be serving as the department chairperson that semester, mentioned that he had received a phone call from a newspaper reporter asking about the question. The professor sketched out the problem for us, and said, "I told him that, of course the answer was x." Naturally as soon as class was over, several of us students who had read about the problem over the weekend ran up to the professor and explained to him why he was wrong.

For the next week, the problem continued to stir up debate in our math lab. About half the students who looked at it initially believed the answer was x. Most people quickly changed their minds once it was explained to them, but we did have one hold-out who refused to budge. If I remember correctly, he was a Ph.D. candidate in differential geometry, who insisted that since he had advanced training in a geometrical field, we should defer to his judgment on the problem.

(Now, as to what x and y are... You have almost certainly figured out the correct values for those by now. If you are still unsure, though, I'll put a hint in the comments for you.)

A Short Note on the Halting Problem

Over at Shtetl-Optimized, Scott Aaronson recently had an open thread where he invited readers to pose questions for him (this apparently is what Scott considers relaxation after a hard week). There was an interesting exchange in the comments that caught my eye, but since Scott has already closed the comments on that post, I thought I'd write about it here.

A commenter named Abel posed the following question:

Are there any interesting results concerning subsets of Turing Machines for which the Halting Problem can be solved?

For example, it is trivial to see that machines for which you cannot go back to a previously visited state do not halt. But it would be interesting if there were any non-trivial result for a subset in which there are both machines that halt and that doesn’t halt.

A little further down in the comments, Scott replies that a reader has emailed a response:

Matthew P. Johnson writes in to answer Abel’s question, on whether there exists a “nontrivial” but structurally-defined subset of Turing machines for which the halting problem is decidable:

Supposedly, the subset is extremely close to trivial, i.e., almost all of them (!):
“The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (i) B has asymptotic probability one, so that as the number of states n increases, the proportion of all n-state programs that are in B goes to one; (ii) B is polynomial time decidable; and (iii) the halting problem H intersect B is polynomial time decidable. The proof is sensitive to the particular computational model.”
“The halting problem is decidable on a set of asymptotic probability one”
http://arxiv.org/abs/math/0504351

Since that's a seemingly remarkable result, I'd like to look at it a little closer, and then offer a different response to Abel's original question.

The halting problem is decidable on a set of asymptotic probability one is written by Joel David Hamkins and Alexei Miasnikov, both of the City University of New York. The paper appears to be based on a talk by Hamkins at the Fall 2004 CUNY Logic Workshop.

Since they mention that their proof is sensitive to the particular computational model they use (actually, it would be more precise to say result instead of proof), let's start by taking a look at that. They use a fairly standard, if bare-bones, Turing Machine model. Their TM uses an alphabet consisting of {0,1} and a single tape which extends infinitely to the right.If Q is the set of (non-halting) states of the TM, then the transition function is given by:

δ: Q×{0,1} → (Q ∪ {halt})×{0,1}×{L,R}.

This allows the easy calculation that for a given size n (of number of states), there are (4(n+1))²ⁿ distinct TMs.

Now we come to the one little (but critical) feature of their model: if the head is located on the left-most cell, and the TM attempts to move the head to the left, then the computation fails in a non-halting condition. (We can suppose that this TM is implemented in Windows NT, and instead of failing gracefully, we get a "blue screen of death" when the TM attempts an illegal move.) We're ready to look at their main result.

Define B to be the set of TMs that, on an input tape initialized to all zeros, either halt or fall off the left edge of the tape before repeating a state.

Now, I imagine you can already see where this is going. We can obviously tell if an arbitrary TM is an element of B and if so whether it halts or not, by simply simulating it for n steps. (I wouldn't call that a structural property of the TM, but in fairness the authors do not describe it that way, either.) The only interesting question is whether B has asymptotic probability one. For this, the authors invoke a result on random walks due to Polya:

In the random walk with equal likelihood of moving left or right on a one-way infinite tape, beginning on the left-most cell, the probability of eventually falling off the left edge is 1.

This can be seen intuitively by imagining the behavior of the TM's tape head. At each step it can move either left or right. Assuming the TM doesn't halt first, as n gets larger it becomes increasingly likely that the head will return to the starting point; and each time it does there is a 50% chance it will fall off the left edge on the next step. There is some work involved in making this into a rigorous argument, but basically that's the entire paper right there. (By the way, for some more interesting background on random walks, see Brian Hayes' recent post at bit-player.)

I wouldn't blame you if you find that result less than satisfying.

I think I can offer a somewhat more satisfying answer for Abel. The canonical example of a computing model for which the halting problem is decidable is the linear-bounded automata, or LBA. In an LBA, as well as other space-bounded models, it is possible to tell if a TM is going to loop by simply letting it run long enough to exhaust all possible configurations. It is possible to enforce this syntactically for arbitrary TMs by adopting some conventions for the presence of an outer "control module" that enforces tape boundaries, etc. This same approach also works for syntactically checking for membership in time-bounded classes like P and NP, although of course the halting question is moot for those classes.

This agrees with our intuition about real-life computing. Physical computers are, as a practical matter, space-bounded machines, and they may as well be treated as time-bounded also. For most algorithms we have a pretty good idea of how long they should run, and if a computer program is taking too long to finish we don't hesitate to pull the plug on it and start examining our code for where we screwed up.