Computer Science Events

Apr 11

CS Tea Talk

Complexity of Computing Real Numbers -- Titus Klinge, visiting assistant professor of Computer Science, will lead this discussion.

Thursday, April 11th, 2019
4:00 – 5:00 pm / CMC 301

There are fewer Python programs than real numbers, which means most real numbers are *uncomputable*  What are the implications of this?  Are common irrational numbers such as \sqrt{2}, e, and \pi computable?

In this talk, we explore some elementary computable analysis, including Turing's own definition of computable real numbers.  We will discover that some numbers can be computed more efficiently than others and discuss Hartmanis and Stearns long-standing conjecture that \sqrt{2} cannot be computed in "real time."  We will also introduce Shannon's *general purpose analog computer* (GPAC), compare it with traditional digital models of computation, and investigate how we can compute real numbers with analog devices.

Sponsored by Computer Science Department. Contact: Paula Stowe, x5748