Warwick Mathematics and Philosophy talk: Computing from oracles and uncountable cardinals

  • Andrew D Brooke-Taylor (Speaker)

Activity: Participating in or organising an event types › Invited talk

Description

Warwick Mathematics and Philosophy talk: Computing from oracles and uncountable cardinals

Abstract: Given an infinite string of 0s and 1s - an "oracle" - one can ask what can be computed from it, when you give your computer the ability to query what the nth bit is for any n. There are many results in the literature relating different properties of such oracles, mostly arrived at in an ad hoc manner, but I will show how many of them can be organized in a systematic way. This is done by analogy with so-call cardinal characteristics of the continuum, which are very well-studied (definitions for) uncountable cardinals that may be strictly less than the cardinality of the reals. Inequalities between these cardinals correspond to implications between properties of oracles, and whilst imperfect the analogy is instructive, highlighting some natural open questions.
Period26 Jan 2015
Event typeConference

Keywords

  • set theory
  • computability theory

Documents & Links

Related content