10
$\begingroup$

Is there a notion of computability on sets other than the natural numbers? For the sake of argument, let's say on sets $S$ that biject with $\mathbb{N}$.

It's tempting to say "yes, they are those functions of the form $g \circ f \circ g^{-1}$ where $g$ is any bijection $\mathbb{N} \to S$ and $f$ is any computable function $\mathbb{N} \to \mathbb{N}$". I'm cautious of this definition for two reasons.

  1. It privileges $\mathbb{N}$ over other countable sets. Why is $\mathbb{N}$ special when it comes to defining computability? I'd like a "coordinate free" definition of computability without reference to any privileged set in the same way I might like a "coordinate free" definition of a linear algebra concept without reference to any privileged basis.

  2. It raises questions about the choice of $g$. I suspect it may be possible to find contradictions by particularly pathological choices of $S$ and $g$. For example if I choose $S = \mathbb{N}$ and $g$ some non-computable bijection is it really the case that $g \circ f \circ g^{-1}$ is computable for all computable $f$?

    It's tempting to require in the definition that $g$ be computable but unfortunately that's begging the question.

Is there some general way of describing computability on countable sets other than $\mathbb{N}$?

$\endgroup$
  • 1
    $\begingroup$ Well, aside from $\mathbb{N}$, computability is also often defined on $\Sigma^*$, where $\Sigma$ is a finite alphabet... But again, those definitions differ by a computable bijection $\mathbb{N} \to \Sigma^*$ (that is, in one direction it's computable using the $\mathbb{N}$ definition, and it's inverse is computable using the $\Sigma^*$ definition). So you definitely can do it, where your $g$ and $g^{-1}$ are both computable, but I agree that's begging the more general question... $\endgroup$ – Joshua Grochow Dec 1 '17 at 15:36
  • 1
    $\begingroup$ What about model of computations like tiling systems, cellular automata, tag systems, and so on? $\endgroup$ – Marzio De Biasi Dec 1 '17 at 17:58
  • 2
    $\begingroup$ Why should we not privilege $\mathbb{N}$ over other countable sets? We have an extremely strong reason to do so: CPUs, i.e. the thing that does computation, works on $\mathbb{N}$ (or finite strings over $\mathbb{B}$ which is essentially the same thing). Sure you can choose other sets, but why should anyone accept your definition? How do you justify any claim that what you call computability really is, except by relating it to computation on $\mathbb{N}$, i.e. CPUs? $\endgroup$ – Martin Berger Dec 2 '17 at 14:29
  • 1
    $\begingroup$ @Martin, I give an argument in my answer that we privilege $\{0,1\}^*$ over $\mathbb{N}$ at least to a certain extent with regards to time complexity. The reason this is wrong without some introspection is that we might assume certain results are natural when they're actually just artifacts of the model. $\endgroup$ – Dan Brumleve Dec 2 '17 at 16:37
  • 1
    $\begingroup$ Is there some reason you're limiting attention just to countable sets? $\endgroup$ – Andrej Bauer Dec 3 '17 at 18:03
12
$\begingroup$

This question is not research-level, but since it is receiving answers, I would like to offer an answer that may actually clear things up a bit, and provide references.

There is an entire area of theoretical computer science which studies computability in analysis, algebra and topology. Of central importance is the notion of computability for real numbers. In fact Turing's original paper on Turing machines starts with the following sentence:

The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.

Sometimes it pays to go back to the source.

There are several ways to set up computability on general sets, of which one of the most general ones is realizability theory. The idea of realizability theory goes back to Kleene's paper On the Interpretation of Intuitionistic Number Theory from 1945, but has since been generalized and developed into a mini-branch of computability, with a good mix of category theory, see for instance Jaap van Oosten's book "Realizability: an introduction to its categorical side" (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).

Let me describe the idea of realizability very briefly, and discuss your "coordinate free" requirement later. Start with a model of computation, such as Turing machines, the $\lambda$-calculus, a programming language, or any other partial combinatory algebra (you can even take certain topological spaces to be "models of computation", this stuff is general). For concreteness, let us consider Turing machines. We code Turing machines by natural numbers, but note that I could have taken some other model of computation, so you should not assume that the use of $\mathbb{N}$ is in any way essential here. (Other possibilities include: the powerset of natural numbers, infinite sequences of natural numbers, the syntax of the untyped $\lambda$-calculus, certain categories of games, etc.)

A computability structure on a set $X$ is given by a relation $\Vdash_X$ between $\mathbb{N}$ and $X$, called the realizability relation, such that for every $x \in X$ there $n \in \mathbb{N}$ such that $n \Vdash_X x$. We call such structures assemblies. This definition directly corresponds to the intuitive idea that some piece of data $n$ respresents, or realizes, an element $x \in X$. (For instance, certain sequences of bits represent finite lists of pairs of strings of characters.)

Given two assemblies $(X, {\Vdash_X})$ and $(Y, {\Vdash_Y})$, a map $f : X \to Y$ is realized (or "computable") if there is a Turing machine $T$, such that, whenever $n \Vdash_X x$ then $T(n)$ terminates and $T(n) \Vdash_Y f(x)$. Again, this is a direct transliteration of what it means informally to "program" an abstract function $f$: the corresponding Turing machine does to representing data whatever $f$ does to the corresponding elements.

Assemblies may be extended to a realizability topos. A topos is a model of higher-order intuitionistic mathematics. This tells us that every realizability topos (there is one for each model of computation) contains lots of interesting objects. For instance, it contains an object of real numbers, which thus gives us computability on reals. But it also contains many other objects, such as Hilbert spaces, Banach spaces, spaces of smooth maps, etc. You asked for some other computable structure, but you got something much better: entire mathematical worlds of computability.

Since category theory and toposes can be scary and require some amount of technical proficiency in computability theory, category theory, and logic, we could also work in just one concrete topos, but we express everything in concrete non-abstract ways. A particularly good world of computation arises from Kleene's function realizability, and goes under the name of computable analysis.

Let me comment on the "coordinate free" requirement:

  • Switching between models of computation gives different kinds of computable worlds. This is a bit like switching between different fields giving different kinds of linear algebra.

  • A set $X$ may be equipped with many computability structures $\Vdash_X$, just like a set of vectors has many bases. However, while all bases are equivalent, not all computability structures on $X$ are computably equivalent.

  • If we work concretely with computability structures $(X, {\Vdash_X})$, that is a bit like working with matrices in linear algebra. It can be very useful, but is not abstract.

  • To work in a "coordinate-free" fashion, we work in a realizability topos and harness the power of category theory (yes, it's a cliché but it works).

  • We can even work in a "world-free" fashion: develop mathematics in intuitionistic logic, and then interpret the results in realizability toposes.

$\endgroup$
  • $\begingroup$ I don't see the choice of $\mathbb{N}$ here as analogous to the choice of $\mathbb{R}$ as the field over which we might consider vector spaces. Rather this notion of "realizability relation" seems to me like defining what it means to be measurable by defining the Borel measure on $\mathbb{R}$ and then declaring "a measurable space is anything that bijects with $\mathbb{R}$ and a measurable function is anything which induces a measurable map $\mathbb{R} \to \mathbb{R}$. $\endgroup$ – Tom Ellis Dec 3 '17 at 18:33
  • $\begingroup$ Measurable spaces arise naturally out of (some) topological spaces and it's generally considered a theorem that the non-discrete ones are measurably isomorphic to $\mathbb{R}$. What I'd ideally like to find is the computation theory analogue of the former construction. What's the underlying structure that gives rise to something you can compute on? A correspondence with $\mathbb{N}$, imposed by fiat, isn't particularly satisfying. $\endgroup$ – Tom Ellis Dec 3 '17 at 18:38
  • $\begingroup$ There is no "choice of $\mathbb{N}$", there is only choice of a model of computation. If by "choice of $\mathbb{N}$" you mean "let us use Turing machines (coded by numbers)", then my point is this: for each choice of computability structure $\mathbb{S}$ you get a realizability topos $\mathrm{RT}(\mathbb{S})$. This is analogous to: for each choice of a field $F$ you get the category $\mathrm{Vect}_F$ of vector spaces over $F$. $\endgroup$ – Andrej Bauer Dec 3 '17 at 18:40
  • $\begingroup$ Imposing measures on sets is indeed a bit like imposing computability structures on sets. And in both cases some sets have natural structures associated with them. $\endgroup$ – Andrej Bauer Dec 3 '17 at 18:41
  • 2
    $\begingroup$ Dear Andrej, let me thank you for your considered responses. I'm delighted that a 20 year veteran of the field would take time to enlighten a neophyte like myself rather than voting to close my question as pointless. I'm also pleased to infer that topos theory and the pages on the nLab are now considered accessible to those at the pre-research level. $\endgroup$ – Tom Ellis Dec 4 '17 at 11:56
4
$\begingroup$

The two papers below develop a notion of computability for arbitrary sets. Interestingly even a notion of complexity theory can be defined for this model of computation.

Cobham Recursive Set Functions and Weak Set Theories Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Subset-Bounded Recursion and a Circuit Model for Cobham Recursive Set Functions Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

$\endgroup$
0
$\begingroup$

There is a concept of complexity and computation over the reals. A textbook I would direct you to is: https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

I know of one lab that studies this specifically: https://complexity.kaist.ac.kr/

$\endgroup$
  • $\begingroup$ That one is not particularly realistic as it implies that the Halting oracle is computable. $\endgroup$ – Andrej Bauer Dec 3 '17 at 17:23
-1
$\begingroup$

This is similar to how we define computability in terms of Turing machines and then promptly forget about Turing machines. Since it turns out a Turing machine is as good a definition as any other, we use it as an anchor for an entire equivalence class of models, and we end up with the same class no matter which element we generate it from. Basically this is the Church-Turing thesis and it defines the set of computable bit strings.

Similarly, to define computability on a different set $S$, we anchor it with a particular partial function from bit strings to $S$. Actually it does not matter if this function is a bijection or an injection or any other type of function (for a case where we don't really want it to be an injection, consider a group defined by its presentation where we don't have a unique representation for its elements). It doesn't even have to be a surjection if we permit that singleton sets can be uncomputable. By composing this function with any computable bijection from bit strings to bit strings (a concept already defined), we get a definition of computability for $S$ that's invariant with respect to the function we originally picked (as long as we picked something reasonable). That is, a CT thesis for our set $S$. But if we don't pick a reasonable function, we get a different definition of computability.

This function also serves to define the computability of other functions with domain or range equal to $S$. By changing the range to $S$, keeping the domain as $\{0,1\}^*$, we also get an $O(1)$-invariant definition of Kolmogorov complexity for $S$. And we can finally say that the function we have chosen is itself computable.

So I think the answer to your question is NO. We have to define computability for each set that we want to talk about, because there are non-equivalent definitions. Aside from a very technical or pedagogical discussion it shouldn't be necessary, since a reasonable person can imagine a reasonable definition independently.

But wait, let $S$ be a countably infinite set, and that's it. What's our reasonable definition of computability for $S$? Knowing that the set of bijections between $S$ and $\{0,1\}^*$ is non-empty doesn't tell us which are reasonable. We're out of luck without more details.

And we may encounter multiple inequivalent but equally-reasonable alternatives. Suppose every tree has some number of red leaves and some number of green leaves, and that for every $r \in \mathbb{N}$ there exists exactly one tree with $r$ red leaves, and that for every $g \in \mathbb{N}$ there exists exactly one tree with $g$ green leaves. Both bijections are reasonable in the sense that we can count the leaves and distinguish the colors, and we can walk aimlessly around the woods counting leaves on trees until we find the tree with exactly $23$ green leaves, or the one with $23$ red leaves. It's not clear whether to identify a tree using its red leaf count or its green leaf count because this choice leads to inequivalent definitions of computability for sets of trees. If we instead make our definition by combining the counts with a computable pairing function bijective from $\mathbb{N}^2$ to $\mathbb{N}$ (having appropriately defined computability on $\mathbb{N}^2$), that also uniquely identifies each tree, but the situation is even worse because this is not a bijection between trees and $\mathbb{N}$, now maybe all computable sets of trees are finite!

So in order to avoid the entire discussion it should be understood not only that there exists a reasonable definition of computability on the set in question, but also that there is exactly one class of reasonable definitions.

I think the situation becomes a lot more interesting if we bring time complexity into the picture. Even when just considering integers, our choices matter more. For example, what if we wanted to represent each number as a sum of four squares? We can find such a representation, starting from a base representation, in expected quadratic time with access to randomness. Or instead, as a list of its prime factors, which may or may not be possible to compute in polynomial time. To the extent that we allow hard representations, we lose precision in time complexity. For example, we can't meaningfully say that some function $F:\mathbb{N} \rightarrow \mathbb{N}$ is computable in quadratic time if we have a representation of $\mathbb{N}$ that might require more than quadratic time to convert to or from a base representation. I think this perspective reveals that base representation is a somewhat arbitrary standard. (Standard in the sense that base representation is what anyone has in mind when they say something like "$F:\mathbb{N} \rightarrow \mathbb{N}$ is computable in quadratic time", if the underlying model is one that computes bit strings from bit strings and we're supposed to infer the meaning.)

$\endgroup$

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.