Is there a notion of computability on sets other than the natural numbers?

Question

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}$?

Answer 1

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.

Answer 2

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.

Answer 3

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/

Answer 4

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.)