Blog Archives

Topic Archive: infinitary computability

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.

NERDS: New England Recursion & Definability SeminarSunday, March 30, 20142:00 pmAcademic Center, Room 113, Olin College

Jesse Johnson

Quasiminimality and computability

Westfield State University

We briefly define computability on uncountable domains via Σ1-recursion, with an emphasis on ω1-computability. We will then apply this notion of uncountable computability to quasiminimal excellent classes. We will concentrate on the pseudo-exponential fields and the topological group covers of the complex numbers. We show that the group covers are relatively ω1-computably categorical while the pseudo-exponential fields are not even ω1-computably categorical.

Peter Koepke
Rheinische Friedrich-Wilhelms-Universität Bonn
Prof. Dr. Peter Koepke undertakes research in set theory and logic as a part of the Bonn Mathematical Logic Group.  He earned his Ph.D. in 1984 and Habilitation in 1990 at Freiburg University.   His specific research interests include axiomatic set theory, including infinitary combinatorics, forcing and core models, consistency strengths without the axiom of choice, large cardinals; constructibility theory, including ordinal computability theory and new fine structure theories;  descriptive set theory and infinitary game theory; and general logic, including automated theorem proving and proof checking, such as in the NAPROCHE natural language proof-checking system.
Philip Welch
University of Bristol
Professor Welch (Professor of Mathematical Logic, University of Bristol) conducts research on a broad selection of topics in mathematical and philosophical logic. In set theory, he is a leading researcher on the topics of fine structure and core models, problems concerning determinancy, large cardinals and strong axioms of infinity. He has worked in the philosophy of mathematics on the foundations of set theory and theories of truth. And he has been a central figure in the recently intensified work on infinitary models of computation.
Joel David Hamkins
The City University of New York
Professor Hamkins (Ph.D. 1994 UC Berkeley) conducts research in mathematical and philosophical logic, particularly set theory, with a focus on the mathematics and philosophy of the infinite.  He has been particularly interested in the interaction of forcing and large cardinals, two central themes of contemporary set-theoretic research.  He has worked in the theory of infinitary computability, introducing (with A. Lewis and J. Kidder) the theory of infinite time Turing machines, as well as in the theory of infinitary utilitarianism and, more recently, infinite chess.  His work on the automorphism tower problem lies at the intersection of group theory and set theory.  Recently, he has been preoccupied with various mathematical and philosophical issues surrounding the set-theoretic multiverse, engaging with the emerging debate on pluralism in the philosophy of set theory, as well as the mathematical questions to which they lead, such as in his work on the modal logic of forcing and set-theoretic geology.