I'm curious what the right abstraction is for equipping an arbitrary set with "something kind of like computability".

Topologies don't seem to fit because the complement of an open set is not open in general.

Sigma algebras don't seem to fit because computable functions on real numbers can't "zero in" on a particular real under our intuitive notion of computability. We can construct narrower and narrower sets containing the real in question, but can't isolate the real itself.

Most of the definitions of computability that I've seen before involve defining a subset of $\mathbb{N} \to \mathbb{N}$ or $(\mathbb{N})^n \to \mathbb{N}$. One constructs Turing Machines and describes how to feed data in and read it back out, or considers an initial pool of functions and closes them under certain operators.

There are a couple of properties that apply to functions in $\mathbb{N} \to \mathbb{N}$ that are vaguely computability-like.

  • computability itself: corresponding to an always-halting Turing Machine / decider.
  • computable in polynomial time.
  • capable of being expressed in a particular total functional programming language.

Each of these properties, even though they apply to maps from $\mathbb{N}$ to itself, readily give us a notion of which subsets of $\mathbb{N}$ are computable, namely the preimages of $0_{\mathbb{N}}$ in any of the maps.

However, for certain things like the real numbers $\mathbb{R}$, I can think of two obvious ways to talk about computability, i.e. two candidates for $(\mathbb{R}, \sigma)$ .

  • 1) Restrict our attention to the computable reals. Each of the sets in our collection of subsets $\sigma$ is a subset of the computable reals. Not every subset of the set of computable reals is in $\sigma$, however.

  • 2) Consider "computably distinguishable" reals. Restrict our attention to the interval $[0,1]$, i.e. interpret infinite bitstrings as a real number on the unit interval. As our "basis" of sorts, consider numbers starting with the same finite sequence of 0s and 1s . Consider all finite sequences of finite bistrings. Associate each bitstring with the interval in $[0,1]$ that it corresponds to. By taking reciprocals and using negation, we can map portions of $\mathbb{R}$ back to $[0,1]$ . We then say that our computable subsets in $\mathbb{R}$ have to be computable in $[0,1]$ when $\lambda x . -x$ or $\lambda x . 1/x$ is applied and the result is intersected with $[0,1]$

Is there a kind of additional structure that we can endow a set with to "fix" our notion of computability up front?


The Blum–Shub–Smale machine is a model of computation intended to describe computations over the real numbers. See the original paper [1], but there is now a huge literature on this model.

[1] Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21, Number 1 (1989), 1-46.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.