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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.