Saturday, February 28, 2009

Recognizing/printing real numbers in real time

In the first blog post for the course, on the history of complexity, I saw mention of the question of whether the number $\sqrt{2}$ could be printed out by a Turing Machine at a rate of $O(1)$ time per digit. I had never heard of the problem before. Apparently one can ask similar questions about recognizing in "real time" whether a number is, say, $\sqrt{2}$; for more, see this post on Dick Lipton's blog.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.