Blog Archives

Topic Archive: computable analysis

CUNY Logic WorkshopFriday, December 2, 20162:00 pmGC 6417

Reed Solomon

Weihrauch reducibility and Ramsey theorems

University of Connecticut

Weihrauch reducibility is a common tool in computable analysis for understanding and comparing the computational content of theorems. In recent years, variations of Weihrauch reducibility have been used to study Ramsey type theorems in the context of reverse mathematics where they give a finer analysis than implications in RCA0 and they allow comparisons of computably true principles. In this talk, we will give examples of recent results and techniques in this area.

Tuesday, May 13, 20142:30 pm750 Schapiro CEPSR, Columbia University Morningside CampusThe Schapiro Center (CEPSR) is located on the Morningside Campus of Columbia University.

Russell Miller

Generalizing Turing machines: $\omega_1$-computation

City University of New York

While Turing machines are well established as the principal framework for theoretical computation on the natural numbers, no machine model for computation on uncountable domains has achieved any similarly dominant status. We will give an overview of various methods that have been explored, including computable analysis, the Blum-Shub-Smale model of computation on the real numbers, local computability, α-recursion theory, and certain models of computation over ordinal time (one of which turns out to be equivalent to α-recursion). Each of these has strengths and weaknesses, for which reason no one of them has come to dominate the discussion. Much of the talk will be expository, describing these different notions of computation, but we will finish with a specific example from ω1-recursive model theory which shows how phenomena that were unknown under Turing computation on ω can arise in the context of ω1-computable model theory.