Is there a notion of computability on sets other than the natural numbers? 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 &quot;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}$&quot;.  I'm cautious of this definition for two reasons.

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

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